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).