Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | 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 AM
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