arXiv preprint ·
Fresh-Priority Eviction for Cuckoo Filters: Exploiting Latent Randomness Under XOR Hashing
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Cuckoo filters are a widely adopted approximate membership query (AMQ) data structure that supports insertions, lookups, and deletions with low memory overhead. At high load factors, however, insertion performance degrades sharply due to the random-walk eviction process, which may require a large number of element relocations. Recent work on bucketized cuckoo hash tables has shown that \emph{fresh-priority eviction}, which preferentially evicts elements whose alternate bucket location has not yet been used, achieves $O(\ell m)$ total expected evictions for bucket size~$\ell$, an improvement over the standard random walk. In this paper, we show that this technique transfers to \emph{cuckoo filters} despite their use of XOR-based partial-key hashing. The key insight is that a fresh element's fingerprint, although stored in the table, is not examined by the eviction policy, so when the fingerprint length satisfies $k = Ω(\log m)$, the alternate bucket hash remains a near-uniform random variable, a property we call \emph{latent randomness}. We prove that under this condition the corruption graph remains subcritical and the total number of evictions is $O(\ell m \log m)$; we conjecture the tighter $O(\ell m)$ bound holds via the full amortized analysis of Bell and Kuszmaul. We further propose encoding the fresh/kicked state implicitly by the element's position within its bucket, requiring no additional per-element metadata. Experimental results on a filter with $2^{22}$ slots and $8$-bit fingerprints demonstrate $1.2\times$ to $2.4\times$ fewer evictions at load factors between $94\%$ and $99\%$ for bucket size $\ell = 8$, and a $1.73\times$ reduction in cumulative evictions to full capacity.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.