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

## 1 comment:

When do we get to see your papers?

Post a Comment