Publications

### Server    domino.mpi-inf.mpg.de

 Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop
 Author, Editor
 Editor(s): Alt, Helmut Habib, Michel dblp dblp
 BibTeX cite key*: FPSS03
 Title, Booktitle
 Title*: Space Efficient Hash Tables with Worst Case Constant Access Time d-cuckoo.ps (201.27 KB) Booktitle*: Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003)
 Event, URLs
 Conference URL:: http://page.inf.fu-berlin.de/~stacs03/ Downloading URL: Event Address*: Berlin, Germany Language: English Event Date* (no longer used): February, 27 - March, 1 Organization: Event Start Date: 1 January 1999 Event End Date: 1 January 1999
 Publisher
 Name*: Springer URL: http://www.springer.de/ Address*: Berlin, Germany Type:
 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 2607 Number: Month: February Pages: 271-282 Year*: 2003 VG Wort Pages: 28 ISBN/ISSN: 3-540-00623-0 Sequence Number: DOI:
 (LaTeX) Abstract: We generalize Cuckoo Hashing \cite{PagRod01} to \emph{$d$-ary Cuckoo Hashing} and show how this yields a simple hash table data structure that stores $n$ elements in $(1+\epsilon)\,n$ memory cells, for any constant $\epsilon > 0$. Assuming uniform hashing, accessing or deleting table entries takes at most $d = O(\ln\frac{1}{\epsilon})$ probes and the expected amortized insertion time is constant. This is the first dictionary that has worst case constant access time and expected constant update time, works with $(1+\epsilon)\,n$ space, and supports satellite information. Experiments indicate that $d=4$ choices suffice for $\epsilon \approx 0.03$. We also describe a hash table data structure using explicit constant time hash functions, using at most $d= O(\ln^2\frac{1}{\epsilon})$ probes in the worst case. A corollary is an expected linear time algorithm for finding maximum cardinality matchings in a rather natural model of sparse random bipartite graphs. Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{FPSS03,
AUTHOR = {Fotakis, Dimitris and Pagh, Rasmus and Sanders, Peter and Spirakis, Paul G.},
EDITOR = {Alt, Helmut and Habib, Michel},
TITLE = {Space Efficient Hash Tables with Worst Case Constant Access Time},
BOOKTITLE = {Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003)},
PUBLISHER = {Springer},
YEAR = {2003},
VOLUME = {2607},
PAGES = {271--282},
SERIES = {Lecture Notes in Computer Science},