Teaching materials

Cuckoo Hashing for Undergraduates
Lecture note, March 2006

Talks (with no paper)

Will the I/O model survive till the 22nd century?
Presented at the Dagstuhl seminar on Cache-oblivious and cache-aware algorithms, July 2004.

Journal papers

A Trade-Off for Worst-Case Efficient Dictionaries [ abstract | pdf | ps | bib ]
Nordic Journal of Computing 7 (2000), pp. 151-163. (Special issue for SWAT 2000.)
Conference version [ slides ] appeared in proceedings of SWAT 2000, Lecture Notes in Computer Science 1851, p. 22-31. © Springer-Verlag.

Low Redundancy in Static Dictionaries with Constant Query Time [ abstract | pdf | ps | bib ]
SIAM Journal on Computing 31 (2001), pp. 353-363.
Conference version [ slides ] appeared in the proceedings of ICALP '99, Lecture Notes in Computer Science 1644, p. 595-604. © Springer-Verlag.

Deterministic Dictionaries [ abstract | pdf | ps | bib | IDEAL ]
With Torben Hagerup and Peter Bro Miltersen.
Journal of Algorithms 41 (2001), pp. 69-85. © 2001 by Academic Press.
Conference version [ slides ] of part of this paper appeared in the proceedings of SODA 2000, p. 487-493. © ACM-SIAM.

Fast Random Access to Wavelet Compressed Volumetric Data Using Hashing [ abstract | pdf | ps | bib ]
With Flemming Friche Rodler.
Accepted for ACM Transactions on Graphics, but pending revision.

Cuckoo Hashing [ abstract | pdf | ps | source | slides | Wikipedia]
With Flemming Friche Rodler.
Journal of Algorithms 51 (2004), p. 122-144. © 2004 by Academic Press
Short version [bib] appeared in Proceedings of ESA 2001, Lecture Notes in Computer Science 2161, p. 121-133. © Springer-Verlag.

Space Efficient Hash Tables With Worst Case Constant Access Time [ abstract | pdf | slides ]
With Dimitris Fotakis, Peter Sanders, and Paul Spirakis.
Theory of Computing Systems 38(2), p. 229-248. © Springer-Verlag 2005. (Special issue for STACS 2003.)
Conference version appeared in Proceedings of STACS 2003, Lecture Notes in Computer Science 2607, p. 271-282. © Springer-Verlag.

Optimality in External Memory Hashing [ pdf ]
With Morten Skaarup Jensen
Algorithmica 52 (3), 2008, p. 403-411. © Springer-Verlag 2008. DOI: 10.1007/s00453-007-9155-x

Uniform Hashing in Constant Time and Optimal Space [ pdf | slides ]
With Anna Östlin.
SIAM J. Comput. 38(1): 85-96 (2008). Conference version appeared in the proceedings of STOC 2003, p. 622-628. © ACM.

Dispersing Hash Functions [ pdf | slides ]
To appear in Random Structures & Algorithms. Short version appeared at RANDOM 2000, Proceedings in Informatics 8, p. 53-67. © Carleton Scientific.

Linear Probing with Constant Independence [ pdf | slides ]
With Anna Pagh and Milan Ruzic.
SIAM Journal on Computing 39(3), 2009. Conference version in proceedings of STOC 2007.

Finding Associations and Computing Similarity via Biased Pair Sampling [ pdf | slides ]
With Andrea Campagna
Submitted to special issue of KAIS, 2010. Conference version in Proceedings of ICDM 2009

Conference papers not appeared in journals

Hash and Displace: Efficient Evaluation of Minimal Perfect Hash Functions [ abstract | pdf | ps | bib | slides ]
Short version appeared in the proceedings of WADS '99, Lecture Notes in Computer Science 1663, p. 49-54. © Springer-Verlag.

On the Cell Probe Complexity of Membership and Perfect Hashing [ abstract | pdf | ps | bib | slides ]
Appeared in the proceedings of STOC 2001, p. 425-432. © ACM.

Optimal Time-Space Trade-Offs for Non-Comparison-Based Sorting [ abstract | pdf | ps | bib | slides ]
With Jakob Pagter
Appeared in proceedings of SODA 2002, p. 9-18. © ACM-SIAM.

One Probe Search [ abstract | pdf | ps | bib | slides ]
With Anna Östlin.
Appeared in Proceedings of ICALP 2002, Lecture Notes in Computer Science 2380, p. 439-450. © Springer-Verlag.

On Adaptive Integer Sorting [ abstract | pdf | slides ] With Anna Pagh and Mikkel Thorup.
Appears in Proceedings of ESA 2004, Lecture Notes in Computer Science 3221, p. 556-567. © Springer-Verlag.

An Optimal Bloom Filter Replacement [ abstract | pdf | bib | slides ]
With Anna Pagh and S. Srinivasa Rao
Appears in proceedings of SODA 2005. © ACM-SIAM.

On Dynamic Range Reporting in One Dimension [ abstract | pdf | slides ]
With "Christian Worm Mortensen and Mihai Pătraşcu.
To appear in the proceedings of STOC 2005. © ACM.
Full version (preliminary) available as arXiv:cs.DS/0502032.

External String Sorting: Faster and Cache-Oblivious [ pdf | slides ] With Rolf Fagerberg and Anna Pagh. Appears in Proceedings of STACS 2006, Lecture Notes in Computer Science. © Springer-Verlag.

De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space) [ pdf | slides ]
With Erik Demaine, Friedhelm Meyer auf der Heide, and Mihai Pătraşcu.
Short version appears in Proceedings of LATIN 2006, Lecture Notes in Computer Science. © Springer-Verlag.

Scalable Computation of Acyclic Joins [ pdf | slides | animated slides ]
With Anna Pagh. To appear at PODS 2006.
 © ACM. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The deinitive version is published in the PODS proceedings.

Deterministic load balancing and dictionaries in the parallel disk model [ pdf | slides]
With Mette Berger, Esben Rune Hansen, Mihai Pătraşcu, Milan Ruzic, and Peter Tiedemann.
To appear in the proceedings of SPAA 2006.
 © ACM. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The deinitive version is published in the SPAA proceedings.

Simple and Space-Efficient Minimal Perfect Hash Functions [ pdf ]
With Fabiano C. Botelho and Nivio Ziviani.
Proceedings of WADS 2007.

Fast evaluation of union-intersection expressions [ pdf | slides ]
With Philip Bille and Anna Pagh
Proceedings of ISAAC 2007, p. 739-750. Full version at arXiv.

Succinct Data Structures for Retrieval and Approximate Membership [ pdf ]
With Martin Dietzfelbinger
Proceedings of ICALP 2008, p. 385-396

Monotone minimal perfect hashing: searching a sorted table with O(1) accesses. [ pdf | slides ]
With Djamal Belazzougui, Paolo Boldi, and Sebastiano Vigna
Proceedings of SODA 2009, p. 785-794.

Theory and Practise of Monotone Minimal Perfect Hashing. [ pdf]
With Djamal Belazzougui, Paolo Boldi, and Sebastiano Vigna
Proceedings of ALENEX 2009, p. 132-144.

Faster join-projects and sparse matrix multiplications [ pdf ]
With Rasmus Resen Amossen
Proceedings of ICDT 2009, p. 121-126

Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes [ pdf | slides ]
With S. Srinivasa Rao
Proceedings of PODS 2009

Storing a compressed function with constant time access [ pdf | slides ]
With Johannes Hreinsson and Morten Krøyer
Proceedings of ESA 2009

Cache-oblivious Hashing [ pdf ]
With Zhewei Wei, Ke Yi, and Qin Zhang
Proceedings of PODS 2010

Other

Basic External Memory Data Structures [ abstract | pdf | ps | bib ]
Chapter in a volume prepared by participants of the GI-Dagstuhl-Forschungsseminar Algorithms for Memory Hierarchies. Appeared in Lecture Notes in Computer Science 2625, p. 14-35. © Springer-Verlag.

Hashing, randomness and dictionaries [ pdf | ps | powerpoint | html slides ]
PhD thesis, University of Aarhus, July 2002, x + 167 pp.

Popular articles (in Danish)

Tetris er svært [ pdf ]
Aktuel Naturvidenskab 4/2002, p. 19.

Kan computere gætte? [ pdf ]
Aktuel Naturvidenskab 3/2001, p. 17-20.

Naturvidenskab@home [ pdf ]
With Jan Gorodkin.
Aktuel Naturvidenskab 4/2001, p. 12-15.

Overbeviselsens kunst [ pdf ]
Aktuel Naturvidenskab 5/2001, p. 14-17, and Jyllandsposten, September 22, 2002.

Notes: The papers may deviate in formatting from published versions, and minor changes may have been made. Any major change (e.g. a longer or updated version) is stated explicitly.
The copyrights for journal and conference proceedings papers generally belong to the publisher. The papers may be downloaded for personal or research purposes only.
Inquiries about the papers are welcome at pagh@it-c.dk.
Home page

Modified: September 10, 2009