SODA / Data Structures

The SODA list of accepted papers, with abstracts, is here.

Here are the clear data structures papers:

• Fully-Functional Succinct Trees (Kunihiko Sadakane, Gonzalo Navarro)
  
  
• On the Cell Probe Complexity of Dynamic Membership (Ke Yi, Qin Zhang)
  
  
• Data Structures for Range Minimum Queries in Multidimensional Arrays (Hao Yuan, Mikhail J. Atallah)
  
  
• A locality-sensitive hash for real vectors (Tyler Neylon)
  
  
• Deletion Without Rebalancing in Balanced Binary Trees (Siddhartha Sen, Robert E. Tarjan)
  
  
• Cache-Oblivious Dynamic Dictionaries with Optimal Update/Query Tradeoff (Gerth Stølting Brodal, Erik D. Demaine, Jeremy T. Fineman, John Iacono, Stefan Langerman, J. Ian Munro)
  
  
• Cell-probe lower bounds for prefix sums and matching brackets (Emanuele Viola)
  + A Lower Bound for Succinct Rank Queries (Mihai Patrascu)
  
  
• Applications of Forbidden 0-1 Matrices to Search Trees and Path Compression-Based Data Structures (Seth Pettie)

The following are also data structures papers, though they can be seen as stradling two areas:

• A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs (Aaron Bernstein) -- the main contribution is better preprocessing time of a data structure
  
  
• Counting Inversions, Offline Orthogonal Range Counting, and Related Problems (Timothy M. Chan, Mihai Patrascu) -- improves the preprocessing and offline times of some data structures
  
  
• Highway Dimension, Shortest Paths, and Provably Efficient Algorithms (Ittai Abraham, Amos Fiat, Andrew Goldberg, Renato Werneck) -- distance oracles are a very important topic in data structures; this paper is more about modelling, though.
  
  
• On the Exact Space Complexity of Sketching and Streaming Small Norms (Daniel M. Kane, Jelani Nelson, David P. Woodruff) -- whenever you talk about streaming and care about time complexity, this is clearly a data structure; if you solve the problem with k-wise independent hash functions, even more so.
  
  
• The 1+β Choice Process and Weighted Balls-into-Bins (Yuval Peres, Kunal Talwar, Udi Wieder) -- more on the power of two choices, though the process is probably unrealistic in a data structures context.
  
  
• Regular Expression Matching with Multi-Strings (Philip Bille, Mikkel Thorup) -- stringology is close enough :)
  
  
• Fast distance multiplication of unit-Monge matrices (Alexander Tiskin) -- also stringology.

I find the number of papers to be on the low side. There are a couple of rejected papers where I may disagree with the wisdom of the PC, but overall I think the numbers just reflect the fact that the field is old, and progress comes hard.

Disclaimer: Note that this list is not so closely correlated with my interests. There are data structure papers that I am not interested in, and many non-data-structures papers that I am interested in (even among my own papers, only half can be found above).