Double Hashing Thresholds via Local Weak Convergence

Mathieu Leconte 1, 2, 3, *
* Corresponding author
2 DYOGENE - Dynamics of Geometric Networks
CNRS - Centre National de la Recherche Scientifique : UMR8548, Inria Paris-Rocquencourt, DI-ENS - Département d'informatique de l'École normale supérieure
Abstract : A lot of interest has recently arisen in the analysis of multiple-choice "cuckoo hashing" schemes. In this context, a main performance criterion is the load threshold under which the hashing scheme is able to build a valid hashtable with high probability in the limit of large systems; various techniques have successfully been used to answer this question (differential equations, combinatorics, cavity method) for increasing levels of generality of the model. However, the hashing scheme analysed so far is quite utopic in that it requires to generate a lot of independent, fully random choices. Schemes with reduced randomness exists, such as "double hashing", which is expected to provide similar asymptotic results as the ideal scheme, yet they have been more resistant to analysis so far. In this paper, we point out that the approach via the cavity method extends quite naturally to the analysis of double hashing and allows to compute the corresponding threshold. The path followed is to show that the graph induced by the double hashing scheme has the same local weak limit as the one obtained with full randomness.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-00933627
Contributor : Mathieu Leconte <>
Submitted on : Monday, January 20, 2014 - 10:04:29 PM
Last modification on : Thursday, October 17, 2019 - 11:58:34 AM
Long-term archiving on : Monday, April 21, 2014 - 5:40:23 PM

File

double_hashing_threshold.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00933627, version 1

Citation

Mathieu Leconte. Double Hashing Thresholds via Local Weak Convergence. 51st Annual Allerton Conference on Communication, Control, and Computing, Oct 2013, Urbana-Champaign, United States. ⟨hal-00933627⟩

Share

Metrics

Record views

417

Files downloads

253