Name
Abstract | ||
|---|---|---|
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 the random-walk heuristic for inserting in an online fashion new items into the hash table. Provided that k >= 3 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 probability 1 - o(1) as the size of the table grows large. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1137/100797503 | SIAM JOURNAL ON COMPUTING |
Keywords | DocType | Volume |
information retrieval,hashing,random graphs and hypergraphs | Journal | 42 |
Issue | ISSN | Citations |
6 | 0097-5397 | 11 |
PageRank | References | Authors |
0.83 | 18 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikolaos Fountoulakis | 1 | 185 | 18.04 |
| Konstantinos Panagiotou | 2 | 290 | 27.80 |
| Angelika Steger | 3 | 995 | 111.50 |