max planck institut
mpii logo Minerva of the Max Planck Society

Efficient Data Structures

  • The course starts on the 17th of April.

Basic Information

Lectures: Monday 10:15-12 and Thursday 10:15-12:00, room 021 (ground floor of the MPI-INF building E1.4)
Lecturers: Paweł Gawrychowski and Mayank Goswami and Patrick Nicholson
Tutorials: Monday 14:15-16:00, room 023 (ground floor of the MPI-INF building)
Tutors: TBD
Exam dates: July 25th 10:30-13:30 room 24 (exam) August 25th 12:15-15:00 room 21 (re-exam)


Efficient data structures are an indispensable tool for the algorithm designer. Such structures are used as building blocks in widely deployed solutions for every day problems, such as text search (e.g., Google), and have revolutionized our ability to process information. Though many textbooks offer a thorough treatment of basic data structures, many important results and techniques are not covered in typical undergraduate courses. In contrast, this course will cover more advanced techniques, both classical and recent, from the area. Though we will cover state of the art techniques, the presentation is relatively self-contained, and only assumes a basic undergraduate data structures course (e.g., knowledge of red-black trees, B-trees, etc.).

Lectures (Topics marked with a * may change slightly depending on time)

Date Topics Lecture notes
Apr 17 Introduction, Implicit Data Structure Model, and Dynamic Dictionaries

[Ref. 1] J.I. Munro, H. Suwanda:
Implicit Data Structures for Fast Search and Update.
J. Comput. Syst. Sci. 21(2): 236-250 (1980)
Implicit DS Slides
Homework Sheet #1
Apr 21 No lecture (Easter Monday)
Apr 24 Dynamic Dictionaries (continued) and Multikey Search

[Ref. 2] G. Frederickson:
Implicit Data Structures for the Dictionary Problem.
J. ACM 30(1): 80-94 (1983)
[Ref. 3] J.I. Munro:
An Implicit Data Structure Supporting Insertion, Deletion, and Search in O(log² n) Time.
J. Comput. Syst. Sci. 33(1): 66-74 (1986)
[Ref. 4] H. Alt, K. Mehlhorn, J.I. Munro:
Partial Match Retrieval in Implicit Data Structures.
Inf. Process. Lett. 19(2): 61-65 (1984)

Possible starting points for projects:
[Ref. 5] G. Franceschini et al.:
Implicit B-trees: a new data structure for the dictionary problem.
J. Comput. Syst. Sci. 68(4): 788-807 (2004)
[Ref. 6] G. Franceschini, R. Grossi:
Optimal Implicit Dictionaries over Unbounded Universes.
Theory Comput. Syst. 39(2): 321-345 (2006)
[Ref. 7] G. Franceschini, R. Grossi:
Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees.
WADS 2003: 114-126
[Ref. 8] G. Brodal, C. Kejlberg-Rasmussen, J. Truelsen:
A Cache-Oblivious Implicit Dictionary with the Working Set Property.
ISAAC (2) 2010: 37-48
[Ref. 9] G. Brodal, C. Kejlberg-Rasmussen:
Cache-Oblivious Implicit Predecessor Dictionaries with the Working-Set Property.
STACS 2012: 112-123
[Ref. 10] G. Brodal, J. Nielsen, J. Truelsen:
Finger Search in the Implicit Model.
ISAAC 2012: 527-536
Implicit DS Slides
Apr 28 Multikey Search (continued) and The Word-RAM Model

[Ref. 11] J. Ian Munro: Searching a Two Key Table Under a Single Key.
STOC 1987: 383-387
[Ref. 12] Larry Carter, Mark N. Wegman: Universal Classes of Hash Functions.
J. Comput. Syst. Sci. 18(2): 143-154 (1979)
[Ref. 13] Michael L. Fredman, János Komlós, Endre Szemerédi: Storing a Sparse Table with 0(1) Worst Case Access Time.
J. ACM 31(3): 538-544 (1984)

Possible starting points for projects:
[Ref. 14] A. Fiat et al. An Implicit Data Structure for Searching a Multikey Table in Logarithmic Time.
J. Comput. Syst. Sci. 43(3): 406-424 (1991)
Homework Sheet #2
Implicit DS Slides
Word-RAM & Succinct DS
May 1 No lecture (Labour Day)
May 5 Rank and Select and Tree Representations

[Ref. 15] Guy Jacobson: Space Efficient Static Trees and Graphs.
In Proc. FOCS 1989. pp. 549-554
[Ref. 16] R. Raman, V. Raman, S. Rao: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets.
ACM Transactions on Algorithms (TALG), 3:4, No 43, 2007.
[Ref. 17] Arash Farzan: Succinct Representations of Trees and Graphs.
In particular Chapter 4. PhD Dissertation, University of Waterloo, 2009.

Possible starting points for projects:
[Ref. 18] M. Patrascu: Succincter In Proc. FOCS 2008.
  ---   Explicit Idea: I would also like see a write up about the Indexable Dictionary (ID) structure Ref. 16. In particular, a list and description of all the hashing techniques used in the structure and related improvements to FKS hashing.
Word-RAM & Succinct DS
May 8 Representations of Graphs

[Ref. 15], [Ref. 17] In particular Chapter 5
[Ref. 19] J. Ian Munro, V. Raman: Succinct Representation of Balanced Parentheses, Static Trees, and Planar Graphs
In Proc. FOCS 1997. pp. 118-126.
Homework Sheet #3
Word-RAM & Succinct DS
May 12 Lower Bounds via the Reciprocal Property

[Ref. 20] Alexander Golynski: Cell probe lower bounds for succinct data structures.
SODA 2009: 625-634

Possible starting points for projects:
  ---   If you are interested in this paper, please come see me to discuss possible projects
Word-RAM & Succinct DS
May 15 Wavelet Trees and Orthogonal Range Search

[Ref. 21] Bernard Chazelle: A Functional Approach to Data Structures and Its Use in Multidimensional Searching.
SIAM J. Comput. 17(3): 427-462 (1988)
[Ref. 22] Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter: High-order entropy-compressed text indexes.
SODA 2003: 841-850
[Ref. 23] Travis Gagie, Simon J. Puglisi, Andrew Turpin: Range Quantile Queries: Another Virtue of Wavelet Trees.
SPIRE 2009: 1-6
Homework Sheet #4
Word-RAM & Succinct DS
May 19 Dynamic Data Structure Models/Memory Management

[Ref. 24] Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, Robert Sedgewick: Resizable Arrays in Optimal Time and Space.
WADS 1999: 37-48
[Ref. 25] Rajeev Raman, S. Srinivasa Rao: Succinct Dynamic Dictionaries and Trees.
ICALP 2003: 357-368 and [Ref. 3] (again)

Possible starting points for projects:
[Ref. 26] Stelios Joannou, Rajeev Raman: An Empirical Evaluation of Extendible Arrays. SEA 2011: 447-458
[Ref. 27] Gonzalo Navarro, Yakov Nekrich: Optimal Dynamic Sequence Representations. SODA 2013: 865-876
Word-RAM & Succinct DS
May 22 Van Emde Boas, x-fast and y-fast trees.

Possible starting points for projects:
[Ref. 28] C. W. Mortensen et al. On dynamic range reporting in one dimension
Homework Sheet #5
May 26 The static structure of Beame and Fich.

Possible starting points for projects:
[Ref. 29] M. Karpinski and Y. Nekrich Predecessor queries in constant time?
Homework Sheet #6
May 29 No lecture (Ascension)
June 2 The static structure continued.

I'm really interested n understanding these two papers:
[Ref. 30] M. Ruzic Making deterministic signatures quickly
[Ref. 31] M. Ruzic Constructing Efficient Dictionaries in Close to Sorting Time
June 5 Fusion trees.

[Ref. 32] A. Andersson et al. Fusion trees can be implemented with AC0 instruction only
[Ref. 33] M. Thorup On AC0 implementations of fusion trees and atomic heaps
Homework Sheet #7
June 9 No lecture (Whit Monday)
June 12 Exponential search trees and introduction to persistence. slides
June 5 Fusion trees.

[Ref. 32] A. Andersson et al. Fusion trees can be implemented with AC0 instruction only
[Ref. 33] M. Thorup On AC0 implementations of fusion trees and atomic heaps
Homework Sheet #7
June 16 Introduction to lower bounds: Decision trees and comparison model, algebraic decision trees.

[Ref. 34] Jeff Erickson's notes on algebraic decision trees
June 19 No lecture (Corpus Christi)
June 23 Algebraic decision trees. Models of Computation 1:Word-RAM, pointer machine, orthogonal range reporting in pointer machine.

[Ref. 35] Michael Ben-Or Lower bounds for algebraic computation trees.
[Ref. 36] Kasper Green Larsen Ph.D. Thesis
[Ref. 37] Bernard Chazelle Lower bounds for orthogonal range searching: the reporting case
Assignment 8
June 26 Indexability model, orthogonal range reporting. Cell probe model membership lower bounds.

[Ref. 38] V.Samoladas, D.P.MirankerA lower bound theorem for indexing schemes and its application to multidimensional range queries
[Ref. 39] A.C.Yao Should tables be sorted?
June 30 The order maintenance problem.

[Ref. 40] M. Bender et al. Two Simplified Algorithms for Maintaining Order in a List
July 3 Making arrays fully persistent.

[Ref. 41] P. Dietz Fully persistent arrays
July 7 Cell probe membership. Communication complexity lower bounds.

[Ref. 42] P.B.MiltersenCell ProBe complexity-a survey
[Ref. 43] Mihai Patrascu's thesis
July 10 Chronogram technique of Fredman and Saks, Bloom filter lower bounds, External memory introduction, searching lower bounds, B-trees.

[Ref. 44] Fredman and Saks The cell probe complexity of dynamic data structures
[Ref. 45] Carter et. al Exact and approximate membership testers
Practice set
Practice set solutions
July 14 No lecture (Mayank is away)
July 17(Moved to July 18) Lower bounds on sorting and permuting, external algebraic decision trees, Buffer trees, the dictionary problem in external memory and lower bounds.

[Ref. 46] Aggarwal and Vitter The Input/Output complexityof sorting and related problems
[Ref. 47] Jeff Erickson's notes on external memory.
July 21 Project discussion.
July 24 Recap.
Prerequisites: An undergraduate course in algorithms is a must. Additionally, some basic familiarity with programming (in any reasonable language) would be welcome.
Class Info: This is a 9-credit-points advanced lecture. There will be two 90 minutes lecture and one 90 minutes tutorial session per week.

More Courses of the Algorithms and Complexity Group

Search MPII (type ? for help)