MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Fotakis, Dimitris
Pagh, Rasmus
Sanders, Peter
Spirakis, Paul G.		dblp
dblp
dblp
dblp
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:
Note, Abstract, ©
(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},
 ADDRESS = {Berlin, Germany},
 MONTH = {February},
 ISBN = {3-540-00623-0},
}

Entry last modified by Christine Kiesel, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Dimitris Fotakis		Created
02/25/2003 16:09:17
Revisions
6.
5.
4.
3.
2.		Editor(s)
Christine Kiesel
Peter Sanders
Christine Kiesel
Dimitris Fotakis
Dimitris Fotakis		Edit Dates
11.06.2004 17:04:33
01/15/2004 07:45:57 PM
26.08.2003 15:04:31
02/25/2003 06:16:17 PM
02/25/2003 04:12:59 PM

File Attachment Icon
d-cuckoo.ps