Metraipolis › archive › dc_d85894ca52df

Fresh-Priority Eviction for Cuckoo Filters: Exploiting Latent Randomness Under XOR Hashing — arXiv:2611.01599

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.01599
License (as archived)
CC0-1.0
Archived
2026-11-03T11:45:39.848Z
SHA-256 of the archived text
7178241f3d9496a572b02bd603f98077101ba1a236830062616bf83b48788a8a
Stable URL of this page
https://metraipolis.com/documento/dc_d85894ca52df

How to cite

Fresh-Priority Eviction for Cuckoo Filters: Exploiting Latent Randomness Under XOR Hashing — arXiv:2611.01599 — arXiv (en), https://arxiv.org/abs/2611.01599 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d85894ca52df (Metraipolis archive dc_d85894ca52df, sha256 7178241f3d9496a572b02bd603f98077101ba1a236830062616bf83b48788a8a)
BibTeX
@misc{dcd85894ca52df,
  title = {Fresh-Priority Eviction for Cuckoo Filters: Exploiting Latent Randomness Under XOR Hashing — arXiv:2611.01599},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.01599},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d85894ca52df; sha256 7178241f3d9496a572b02bd603f98077101ba1a236830062616bf83b48788a8a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01599. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 = \Omega(\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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.01599 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:07:52.237Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).