An analysis of random-walk cuckoo hashing

Alan Frieze, Páll Melsted, Michael Mitzenmacher

Rannsóknarafurð: Kafli í bók/skýrslu/ráðstefnuritiRáðstefnuframlagritrýni

18 Tilvitnanir (Scopus)

Útdráttur

In this paper, we provide a polylogarithmic bound that holds with high probability on the insertion time for cuckoo hashing under the random-walk insertion method. Cuckoo hashing provides a useful methodology for building practical, high-performance hash tables. The essential idea of cuckoo hashing is to combine the power of schemes that allow multiple hash locations for an item with the power to dynamically change the location of an item among its possible locations. Previous work on the case where the number of choices is larger than two has required a breadth-first search analysis, which is both inefficient in practice and currently has only a polynomial high probability upper bound on the insertion time. Here we significantly advance the state of the art by proving a polylogarithmic bound on the more efficient random-walk method, where items repeatedly kick out random blocking items until a free location for an item is found.

Upprunalegt tungumálEnska
Titill gistiútgáfuApproximation, Randomization, and Combinatorial Optimization
Undirtitill gistiútgáfuAlgorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings
Síður490-503
Síðufjöldi14
DOI
ÚtgáfustaðaÚtgefið - 2009
Viðburður12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 - Berkeley, CA, Bandaríkin
Tímalengd: 21 ágú. 200923 ágú. 2009

Ritröð

NafnLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Bindi5687 LNCS
ISSN-númer (prentað)0302-9743
ISSN-númer (rafrænt)1611-3349

Ráðstefna

Ráðstefna12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009
Land/YfirráðasvæðiBandaríkin
Borg/bærBerkeley, CA
Tímabil21/08/0923/08/09

Fingerprint

Sökktu þér í rannsóknarefni „An analysis of random-walk cuckoo hashing“. Saman myndar þetta einstakt fingrafar.

Vitna í þetta