Computer Science – Data Structures and Algorithms
Scientific paper
2010-07-12
Computer Science
Data Structures and Algorithms
14 pages, 8 figures
Scientific paper
Cuckoo hashing with a stash is a robust multiple choice hashing scheme with high memory utilization that can be used in many network device applications. Unfortunately, for memory loads beyond 0.5, little is known on its performance. In this paper, we analyze its average performance over such loads. We tackle this problem by recasting the problem as an analysis of the expected maximum matching size of a given random bipartite graph. We provide exact results for any finite system, and also deduce asymptotic results as the memory size increases. We further consider other variants of this problem, and finally evaluate the performance of our models on Internet backbone traces. More generally, our results give a tight lower bound on the size of the stash needed for any multiple-choice hashing scheme.
Hay David
Kanizo Yossi
Keslassy Isaac
No associations
LandOfFree
Maximum Bipartite Matching Size And Application to Cuckoo Hashing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Maximum Bipartite Matching Size And Application to Cuckoo Hashing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum Bipartite Matching Size And Application to Cuckoo Hashing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-696638