Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  On the Insertion Time of Cuckoo Hashing

Fountoulakis, N., Panagiotou, K., & Steger, A. (2010). On the Insertion Time of Cuckoo Hashing. Retrieved from http://arxiv.org/abs/1006.1231.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
arXiv:1006.1231.pdf (Preprint), 316KB
Name:
arXiv:1006.1231.pdf
Beschreibung:
File downloaded from arXiv at 2014-03-07 11:52
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Fountoulakis, Nikolaos1, Autor           
Panagiotou, Konstantinos1, Autor           
Steger, Angelika1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: Computer Science, Data Structures and Algorithms, cs.DS
 Zusammenfassung: Cuckoo hashing is an efficient technique for creating large hash tables with high space utilization and guaranteed constant access times. There, each item can be placed in a location given by any one out of k different hash functions. In this paper we investigate further the random walk heuristic for inserting in an online fashion new items into the hash table. Provided that k > 2 and that the number of items in the table is below (but arbitrarily close) to the theoretically achievable load threshold, we show a polylogarithmic bound for the maximum insertion time that holds with high probability.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-06-072013-10-102010-06-07
 Publikationsstatus: Online veröffentlicht
 Seiten: 27 pages, final version accepted by the SIAM Journal on Computing
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: arXiv: 1006.1231
URI: http://arxiv.org/abs/1006.1231
BibTex Citekey: Fountoulakis2010
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: