Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Fotakis, Dimitris
Pagh, Rasmus
Sanders, Peter
Spirakis, Paul G.		dblp
dblp
dblp
dblp
Not MPG Author(s):
Fotakis, Dimitris
Pagh, Rasmus
Spirakis, Paul

BibTeX cite key*:

Sanders2005b

Title

Title*:

Space Efficient Hash Tables With Worst Case Constant Access Time

Journal

Journal Title*:

Theory of Computing Systems
Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Springer
Publisher's URL:


Publisher's
Address:

New York, USA
ISSN:


Vol, No, pp, Date

Volume*:

38
Number:

2

Publishing Date:

February 2005

Pages*:

229-248
Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

We generalize Cuckoo Hashing to \emph{$d$-ary Cuckoo Hashing} and show how this yields a simple hash table data structure that stores $n$ elements in $(1+\e)\,n$ memory cells, for any constant $\e > 0$. Assuming uniform hashing, accessing or deleting table entries takes at
most $d=\Oh{\ln\frac{1}{\e}}$ 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+\e)\,n$ space, and supports satellite information. Experiments
indicate that $d=4$ probes suffice for $\e\approx 0.03$.
We also describe variants of the data structure
that allow the use of hash functions that can be evaluated in constant time.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:

http://www.springerlink.com/(p1524t45io1esii3mb3t2aq2)/app/home/contribution.asp?referrer=parent&backto=issue,7,7;journal,10,138;linkingpublicationresults,1:100369,1

Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

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:

@ARTICLE{Sanders2005b,
AUTHOR = {Fotakis, Dimitris and Pagh, Rasmus and Sanders, Peter and Spirakis, Paul G.},
 TITLE = {Space Efficient Hash Tables With Worst Case Constant Access Time},
 JOURNAL = {Theory of Computing Systems},
 PUBLISHER = {Springer},
 YEAR = {2005},
 NUMBER = {2},
 VOLUME = {38},
 PAGES = {229--248},
 ADDRESS = {New York, USA},
 MONTH = {February},
}

Entry last modified by Christine Kiesel, 09/08/2006
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)
Peter Sanders		Created
01/27/2006 10:10:48
Revisions
4.
3.
2.
1.
0.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
08.09.2006 09:11:30
19.06.2006 10:38:47
19.06.2006 10:27:57
19.06.2006 10:24:15
01/27/2006 10:10:48 AM