Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:

http://page.inf.fu-berlin.de/~stacs03/

URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 04:09:17 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
d-cuckoo.ps