Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Bipartite Random Gra ...
Conference paper

Bipartite Random Graphs and Cuckoo Hashing

Reinhard Kutzelnigg (1)
(1) Institute of Discrete Mathematics and Geometry [Vienne]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2005
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
Proceedings
DOI
10.46298/dmtcs.3486
License
https://about.hal.science/hal-authorisation-v1
Indicators
1055
Views
787
Downloads

Bipartite Random Graphs and Cuckoo Hashing

Reinhard Kutzelnigg (1)
(1) Institute of Discrete Mathematics and Geometry [Vienne]
Abstract
The aim of this paper is to extend the analysis of Cuckoo Hashing of Devroye and Morin in 2003. In particular we make several asymptotic results much more precise. We show, that the probability that the construction of a hash table succeeds, is asymptotically $1-c(\varepsilon)/m+O(1/m^2)$ for some explicit $c(\varepsilon)$, where $m$ denotes the size of each of the two tables, $n=m(1- \varepsilon)$ is the number of keys and $\varepsilon \in (0,1)$. The analysis rests on a generating function approach to the so called Cuckoo Graph, a random bipartite graph. We apply a double saddle point method to obtain asymptotic results covering tree sizes, the number of cycles and the probability that no complex component occurs.
Keywords
  • [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • hashing
  • random bipartite graphs
  • generating functions
  • double saddle point method
Cited by

Source: OpenCitations

  • Efficient No-dictionary Verifiable Searchable Symmetric Encryption

    Lecture notes in computer science

    Authors : Wakaha Ogata ORCID, Kaoru Kurosawa

    Journal reference : Volume , 2017, pp. 498-516

    DOI : 10.1007/978-3-319-70972-7_28

  • An Improved Version of Cuckoo Hashing: Average Case Analysis of Construction Cost and Search Operations

    Mathematics in Computer Science

    Authors : Reinhard Kutzelnigg

    Journal reference : Volume 3, 2009, pp. 47-60

    DOI : 10.1007/s11786-009-0005-x

  • Cuckoo Hashing

    Encyclopedia of Algorithms

    Authors : Rasmus Pagh ORCID

    Journal reference : Volume , 2016, pp. 478-481

    DOI : 10.1007/978-1-4939-2864-4_97

  • The Structure of an Evolving Random Bipartite Graph

    Statistical and Machine Learning Approaches for Network Analysis

    Authors : Reinhard Kutzelnigg

    Journal reference : Volume , 2012, pp. 191-215

    DOI : 10.1002/9781118346990.ch7

  • Some Open Questions Related to Cuckoo Hashing

    Lecture notes in computer science

    Authors : Michael Mitzenmacher ORCID

    Journal reference : Volume , 2009, pp. 1-10

    DOI : 10.1007/978-3-642-04128-0_1

  • Cost-Efficient Hashing Index for Cloud Systems

    Big Memory Systems

    Authors : Yu Hua

    Journal reference : Volume , 2025, pp. 197-219

    DOI : 10.1007/978-981-95-2885-1_8

  • An Analysis of Random-Walk Cuckoo Hashing

    Lecture notes in computer science

    Authors : Alan Frieze ORCID, Páll Melsted ORCID, Michael Mitzenmacher ORCID

    Journal reference : Volume , 2009, pp. 490-503

    DOI : 10.1007/978-3-642-03685-9_37

  • MithriLog

    MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture

    Authors : Seongyoung Kang ORCID, Jiyoung An, Jinpyo Kim ORCID, Sang-Woo Jun ORCID

    Journal reference : Volume , 2021, pp. 434-448

    DOI : 10.1145/3466752.3480108

  • More Robust Hashing: Cuckoo Hashing with a Stash

    Lecture notes in computer science

    Authors : Adam Kirsch, Michael Mitzenmacher ORCID, Udi Wieder

    Journal reference : Volume , 2008, pp. 611-622

    DOI : 10.1007/978-3-540-87744-8_51

  • Mitigating Asymmetric Read and Write Costs in System Design

    Big Memory Systems

    Authors : Yu Hua

    Journal reference : Volume , 2025, pp. 221-246

    DOI : 10.1007/978-981-95-2885-1_9

  • Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables

    INDIGO (University of Illinois at Chicago)

    Authors : Alan Frieze ORCID, Páll Melsted ORCID

    Journal reference : Volume 41, 2012, pp. 334-364

    DOI : 10.1002/rsa.20427

  • Private Set Intersection with Linear Communication from General Assumptions

    IACR Cryptology ePrint Archive

    Authors : Brett Hemenway Falk ORCID, Daniel Noble ORCID, Rafail Ostrovsky ORCID

    Journal reference : Volume 2018, 2019, pp. 14-25

    DOI : 10.1145/3338498.3358645

  • No-Dictionary Searchable Symmetric Encryption

    IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

    Authors : Wakaha OGATA ORCID, Kaoru KUROSAWA

    Journal reference : Volume E102.A, 2018, pp. 114-124

    DOI : 10.1587/transfun.e102.a.114

  • History-Independent Cuckoo Hashing

    Lecture notes in computer science

    Authors : Moni Naor ORCID, Gil Segev, Udi Wieder

    Journal reference : Volume , 2008, pp. 631-642

    DOI : 10.1007/978-3-540-70583-3_51

  • Cuckoo Hashing in Cryptography: Optimal Parameters, Robustness and Applications

    Lecture notes in computer science

    Authors : Kevin Yeo ORCID

    Journal reference : Volume , 2023, pp. 197-230

    DOI : 10.1007/978-3-031-38551-3_7

  • Deploying Hash Tables on Die-Stacked High Bandwidth Memory

    ACM Proceedings

    Authors : Xuntao Cheng, Bingsheng He ORCID, Eric Lo ORCID, Wei Wang ORCID, Shengliang Lu ORCID, Xinyu Chen ORCID

    Journal reference : Volume , 2019, pp. 239-248

    DOI : 10.1145/3357384.3358015

  • Cuckoo Hashing

    Encyclopedia of Algorithms

    Authors : Rasmus Pagh ORCID

    Journal reference : Volume , 2015, pp. 1-5

    DOI : 10.1007/978-3-642-27848-8_97-2

  • Cuckoo Hashing

    Encyclopedia of Algorithms

    Authors : Rasmus Pagh ORCID

    Journal reference : Volume , 2008, pp. 212-215

    DOI : 10.1007/978-0-387-30162-4_97
Preview
Loading PDF preview...