Wednesday, September 9, 2009

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

1 comment:

Anonymous said...

When do we get to see your papers?