2011/04/28 by Ely Porat, Porat, Ely, Bar Shalem +1
Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #Caching and Content Delivery #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1104.5400
openalex publication_date 2011/04/28 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
Cuckoo hashing [4] is a multiple choice hashing scheme in which each item can\nbe placed in multiple locations, and collisions are resolved by moving items to\ntheir alternative locations. In the classical implementation of two-way cuckoo\nhashing, the memory is partitioned into contiguous disjoint fixed-size buckets.\nEach item is hashed to two buckets, and may be stored in any of the positions\nwithin those buckets. Ref. [2] analyzed a variation in which the buckets are\ncontiguous and overlap. However, many systems retrieve data from secondary\nstorage in same-size blocks called pages. Fetching a page is a relatively\nexpensive process; but once a page is fetched, its contents can be accessed\norders of magnitude faster. We utilize this property of memory retrieval,\npresenting a variant of cuckoo hashing incorporating the following constraint:\neach bucket must be fully contained in a single page, but buckets are not\nnecessarily contiguous. Empirical results show that this modification increases\nmemory utilization and decreases the number of iterations required to insert an\nitem. If each item is hashed to two buckets of capacity two, the page size is\n8, and each bucket is fully contained in a single page, the memory utilization\nequals 89.71% in the classical contiguous disjoint bucket variant, 93.78% in\nthe contiguous overlapping bucket variant, and increases to 97.46% in our new\nnon-contiguous bucket variant. When the memory utilization is 92% and we use\nbreadth first search to look for a vacant position, the number of iterations\nrequired to insert a new item is dramatically reduced from 545 in the\ncontiguous overlapping buckets variant to 52 in our new non-contiguous bucket\nvariant. In addition to the empirical results, we present a theoretical lower\nbound on the memory utilization of our variation as a function of the page\nsize.\n