跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.26053 · v1

Guided Cuckoo Filter: Full-Pipeline Insertion Optimization

首次提交 2026-11-19 20:59
版本更新 2026-11-19 20:59
雷达观测 2026-11-20 16:53
arXiv ↗PDF ↗

摘要

Cuckoo filters are widely deployed as space-efficient alternatives to Bloom filters, supporting fast lookups, insertions, and deletions. However, their insertion cost grows steeply at high load factors because the standard insertion procedure is entirely unguided: it places each fingerprint into whichever candidate bucket happens to be tried first, and when both candidates are full, it displaces a random victim in a random walk. These blind random choices occur at two distinct stages of the insertion pipeline, the initial placement decision and the eviction victim selection, yet each stage can be independently replaced with a guided, informed decision. We propose the \emph{Guided Cuckoo Filter}, which optimizes the entire insertion pipeline by steering both stages. At the placement stage, the filter compares the occupancy of both candidate buckets and inserts into the less loaded one, applying the power-of-two-choice principle to reduce how often eviction chains are triggered. At the eviction stage, the filter preferentially displaces the most recently inserted element, whose alternate bucket carries latent randomness that shortens the resulting chain. Because these two guided decisions target orthogonal bottlenecks, eviction frequency and eviction chain length, their benefits compose multiplicatively. Experiments on cuckoo filters with 2222^{22} slots confirm that the fully guided insertion reduces per-insertion kicks by up to 3.1×3.1\times at 96\% load and cumulative total kicks by 63\% at the practical capacity ceiling of 95\% load, with negligible computational overhead.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-19 20:59 · 最新观测版本

Guided Cuckoo Filter: Full-Pipeline Insertion Optimization

Cuckoo filters are widely deployed as space-efficient alternatives to Bloom filters, supporting fast lookups, insertions, and deletions. However, their insertion cost grows steeply at high load factors because the standard insertion procedure is entirely unguided: it places each fingerprint into whichever candidate bucket happens to be tried first, and when both candidates are full, it displaces a random victim in a random walk. These blind random choices occur at two distinct stages of the insertion pipeline, the initial placement decision and the eviction victim selection, yet each stage can be independently replaced with a guided, informed decision. We propose the \emph{Guided Cuckoo Filter}, which optimizes the entire insertion pipeline by steering both stages. At the placement stage, the filter compares the occupancy of both candidate buckets and inserts into the less loaded one, applying the power-of-two-choice principle to reduce how often eviction chains are triggered. At the eviction stage, the filter preferentially displaces the most recently inserted element, whose alternate bucket carries latent randomness that shortens the resulting chain. Because these two guided decisions target orthogonal bottlenecks, eviction frequency and eviction chain length, their benefits compose multiplicatively. Experiments on cuckoo filters with 2222^{22} slots confirm that the fully guided insertion reduces per-insertion kicks by up to 3.1×3.1\times at 96\% load and cumulative total kicks by 63\% at the practical capacity ceiling of 95\% load, with negligible computational overhead.

查看此版本解读 →查看此版本原文 ↗