This seminar will offer a glimpse at current frontiers in data structures
research. The main activity will be in-depth examination of recent articles
from leading algorithms and data structures venues, such as SODA, ICALP,
This is a seminar course, so there won't be any formal lectures.
However, everyone is encouraged to watch (most of) the taped lectures from
Eric Demaine's course at MIT
(http://courses.csail.mit.edu/6.851/spring12); you can skip Lectures 2, 5, 6 and 22.
There will be two pieces of assessment, due at the end of each teaching period (16.10 and 04.12).
The first assignment (due 16.10) is to summarize a broad topic in data structures,
providing an introductory overview and list of key references and results. You can use Demaine's
lectures as a guide to these topics, but you're expected to do more than just rewrite the course
Some possible topics are: Persistence, Succinct Data Structues, Graphs, Computational Geometry,
Hashing, External Memory Data Structures, and Data Structures for Integers. Note this is not by any
means an exhaustive list. Note also that some of these areas are very broad, so you're allowed to
pick narrower subtopics where reasonable.
Your eight to 10 page summary will be peer-reviewed by two other students (put another way,
you will review the summaries of two other students, and provide feedback).
Selection of topics. You will spend the first two weeks deciding on your topic. You
should email your preferred topic to us by 16.09. If necessary we will then meet on 18.09
to resolve any collisions. Some overlap between students may be allowed (maximum two students
on one topic), but students must write separate reports, and should work on difference aspects
of the topic.
The second assignment (due 04.12) is to read, digest, and understand a recent piece of data
structures research. This should be an article from a recent conference or journal.
Here is a list of suggested articles to choose from, however you're free
to choose something not on the list, provided you run it past us first.
Assessment will be based on a 30 minute presentation you will give on the paper
you selected (including time for questions). The date of the presentations will be
04.12, possibly in a different venue to C220 (TBA). You must nominate the
article you will present no later than 13.11. In your presentation you should
provide necessary background and motivation for the topic, and then communicate the
key ideas and results of the article. You should try to make your presentation accessible
to everyone in the course.
Use of visual aids, such as slides or the
blackboard, is allowed. You are also free to gather results beyond those presented
in the article to aid your presentation (e.g. by implementing the data structures
and running experiments), but this is not a strict requirement.
Though not compulsory (or even necessary), it might be a good idea to pick your broad
topic so that it helps you with your article. Spend the first couple of weeks purusing
Demaine's lectures and settling on a topic. At the same time, examine the articles and
try to find a handful that fit into one of the broad areas you find interesting.
Confluent persistence revisited
Sebastien Collette, John Iacono, and Stefan Langerman
On the weak prefix-search problem.
Theor. Comput. Sci. 483: 75-84 (2013)
On Cartesian Trees and Range Minimum Queries
Erik D. Demaine, Gad M. Landau, Oren Weimann
Top-k document retrieval in compact space and near optimal time
Gonzalo Navarro, Sharma V. Thankachan
Practical perfect hashing in nearly optimal space
Fabiano C. Botelho, Rasmus Pagh, Nivio Ziviani
Information Systems, 2013
Set-Difference Range Queries
Joseph A. Simons, David Eppstein and Michael Goodrich
Maximizing parallelism in the construction of BVHs, octrees and k-d trees
Proc. High Performance Graphics, 2012
Succinct data structures for representing equivalence classes
Moshe Lewenstein, Ian Munro and Venkatesh Raman
Theory and practice of monotone minimal perfect hashing
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna
Journal of Experimental Algorithmics, 2008
Fingerprints in compressed strings
Philip Bille, Patrick Hagge Cording, Inge Li Gortz, Benjamin Sach, Hjalte Wedel Vildhoj and Soren Vind
Inducing Suffix and LCP Arrays in External Memory
Timo Bingmann, Johannes Fischer and Vitaly Osipov
Tight bounds for sliding Bloom filters
Moni Naor, Eylon Yogev
arXiv, April 2013