1st Symposium on Breakthroughs in Advanced Data Structures (BADS'13)

News

  • The conference takes place in room 236 on 2013-04-11, from 13:00 to 17:30.
  • The proceedings are now online [pdf].
  • Please register on the easychair site (link see below "Submissions"). You should have gotten an invitation from easychair for being a PC member.
  • With your easychair account you can both submit your paper and do all the necessary reviewing work.
  • Please note the 'Important Dates' on easychair. Most importantly, the submission deadline is 2013-03-20, and the reviewing period 2013-03-22 until 2013-04-04.

Formal Matters

If there are multiple papers given for one topic, you should pick ONE result and describe it in great detail (for example, as we do it in the lecture). Your paper can be accompanied by experimental results (either of your own implementation and/or by existing implementations).

The length of your paper should be between 6 and 10 pages using the LIPIcs format. If you need more space (e.g., for experimental results), you can add a clearly marked appendix of unlimited length that will be read at the descretion of the programme committee.

Topics

  • space efficient hash tables: Low Redundancy in Static Dictionaries with O(1) Worst Case Lookup Time by Pagh [SICOMP'01]
  • Bloom filters: Network Applications of Bloom Filters: A Survey by Broder and Mitzenmacher [Internet Mathematics'04] -> Markus Jung
  • order maintenance problem: Two Simplified Algorithms for Maintaining Order in a List by Bender, Cole, Demaine, Farach-Colton, Zito [ESA'02] and reference [3] therein -> Christian Käser
  • skip lists: Determistic Skip Lists by Munro, Papadakis, Sedgewick [SODA'92]
  • splay trees: e.g., chapter 3.9 in Advanced Data Structures by Brass [2008] -> Dominik Messinger
  • exponential search trees: Dynamic Ordered Sets with Exponential Search Trees by Andersson and Thorup [JACM'07]
  • orthogonal 2d range searching: New Data Structures for Orthogonal Range Searching by Alstrup, Brodal, Rauhe [FOCS'00]
  • labeling schemes for distances in trees: Labeling Schemes for Small Distances in Trees by Alstrup, Bille, Rauhe [SIAM J Disc. Maths.'05]-> Philipp Glaser
  • range successor queries: Improved Data Structures for the Orthogonal Range Successor Problem by Yu, Hon, Wang [Computational Geometry: Theory and Applications'11]
  • range median queries: Towards optimal range medians by Brodal, Gfeller, Jørgensen, Sanders [TCS'11]
  • top-k color queries: Top-K Color Queries for Document Retrieval by Karpinksi and Nekrich [SODA'11] and reference [11] therein -> Elias Bordolo
  • range mode queries: Linear-Space Data Structures for Range Mode Query in Arrays by Cha, Durocher, Larsen, Morrison, Wilkinson [STACS'12]
  • space efficient construction of compressed suffix arrays: Breaking a Time-and-Space Barrier in Constructing Full-Text Indices by Hon, Sadakane, Sung [SICOMP'09]
  • dynamic succinct trees: Fully-Functional Static and Dynamic Succinct Trees by Navarro and Sadakane [ACM TALG'12]
  • practical solutions for rank/select: Practical Entropy-Compressed Rank/Select Dictionary by Okanohara and Sadakane [ALENEX'07] -> Michael Axtmann
  • alphabet partitioning for rank/select: Alphabet Partitioning for Compressed Rank/Select and Applications by Barbay, Gagie, Sadakane, Nekrich [ISAAC'10]
  • persistent data structures: e.g., chapter 7.2 in Advanced Data Structures by Brass [2008] or this lecture by E. Demaine -> Felix Kaiser
  • dynamic graphs (dynamic connectivity): e.g., this lecture by E. Demaine -> Marcel Radermacher
  • link-cut trees: e.g., this lecture by E. Demaine -> Alexander Weigl
  • lowest common ancestors in directed acyclic graphs (DAGs): A Path Cover Technique for LCAs in Dags by Kowaluk, Lingas, Nowak [SWAT'08] and references [4], [5], [9], [11], [18] therein

Submissions

Please submit your papers here.