2011/04/27 by Martin Dietzfelbinger, Michael Mitzenmacher, Dietzfelbinger, Martin +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #E.2 #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1104.5111
openalex publication_date 2011/04/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Although cuckoo hashing has significant applications in both theoretical and practical settings, a relevant downside is that it requires lookups to multiple locations. In many settings, where lookups are expensive, cuckoo hashing becomes a less compelling alternative. One such standard setting is when memory is arranged in large pages, and a major cost is the number of page accesses. We propose the study of cuckoo hashing with pages, advocating approaches where each key has several possible locations, or cells, on a single page, and additional choices on a second backup page. We show experimentally that with k cell choices on one page and a single backup cell choice, one can achieve nearly the same loads as when each key has k+1 random cells to choose from, with most lookups requiring just one page access, even when keys are placed online using a simple algorithm. While our results are currently experimental, they suggest several interesting new open theoretical questions for cuckoo hashing with pages.