Double Hashing Thresholds via Local Weak Convergence

Mathieu Leconte 1, 2, 3, *
* Auteur correspondant
2 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
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.
Type de document :
Communication dans un congrès
51st Annual Allerton Conference on Communication, Control, and Computing, Oct 2013, Urbana-Champaign, United States. 2013
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00933627
Contributeur : Mathieu Leconte <>
Soumis le : lundi 20 janvier 2014 - 22:04:29
Dernière modification le : jeudi 11 janvier 2018 - 06:25:34
Document(s) archivé(s) le : lundi 21 avril 2014 - 17:40:23

Fichier

double_hashing_threshold.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00933627, version 1

Collections

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. 2013. 〈hal-00933627〉

Partager

Métriques

Consultations de la notice

291

Téléchargements de fichiers

153