Advanced Data Structures

Course code: 58313302
Credit units: 3

Wednesdays 12-14 in C220

Period I: 04.09-09.10
Period II: 30.10-04.12
"Instructors": Travis GagieJuha KärkkäinenSimon J. Puglisi

General

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, and ESA.

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.

Assessment

There will be two pieces of assessment, due at the end of each teaching period (16.10 and 04.12).

Assignment 1

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

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.

Assignment 2

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.

Suggested Approach

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.

Talk Schedule

27.11.

12:15-13:45

Juho Stenudd
Confluent persistence revisited
Sebastien Collette, John Iacono, and Stefan Langerman SODA, 2012

Junlong Xiang
On the weak prefix-search problem.
Paolo Ferragina Theor. Comput. Sci. 483: 75-84 (2013)

14:15-15:45

Jussi Kokkala
On Cartesian Trees and Range Minimum Queries
Erik D. Demaine, Gad M. Landau, Oren Weimann ICALP 2009

Aleksi Hartikainen
Top-k document retrieval in compact space and near optimal time
Gonzalo Navarro, Sharma V. Thankachan ISAAC, 2013

Heikki Aitakangas
Practical perfect hashing in nearly optimal space
Fabiano C. Botelho, Rasmus Pagh, Nivio Ziviani Information Systems, 2013

4.12.

12:15-13:45

Timo Koivisto
Set-Difference Range Queries
Joseph A. Simons, David Eppstein and Michael Goodrich CCCG, 2013

Peter Hedman
Maximizing parallelism in the construction of BVHs, octrees and k-d trees
Tero Karras Proc. High Performance Graphics, 2012

Jani Rahkola
Succinct data structures for representing equivalence classes
Moshe Lewenstein, Ian Munro and Venkatesh Raman ISAAC, 2013

14:15-15:45

Matthew Pierce
Theory and practice of monotone minimal perfect hashing
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna Journal of Experimental Algorithmics, 2008

Daniel Valenzuela
Fingerprints in compressed strings
Philip Bille, Patrick Hagge Cording, Inge Li Gortz, Benjamin Sach, Hjalte Wedel Vildhoj and Soren Vind WADS, 2013

Dominik Kempa
Inducing Suffix and LCP Arrays in External Memory
Timo Bingmann, Johannes Fischer and Vitaly Osipov ALENEX 2013

Qijia Zeng
Tight bounds for sliding Bloom filters
Moni Naor, Eylon Yogev arXiv, April 2013