Abstract:Approximate membership queries in streams often need recent-window semantics rather than membership over all items ever seen. This paper studies guarded epoch Bloom filters, a sliding-window alternative to counting and stable Bloom filters. The structure partitions a fixed bit budget into rotating epochs, inserts only into the current epoch, clears whole segments at epoch boundaries, and keeps one additional guard epoch. This guard yields a deterministic live-window invariant: every item inserted in the last W positions remains represented, while rotation-induced stale retention is bounded by one epoch beyond the target window. We give the construction, prove its live-coverage and bounded-staleness properties, derive a false-positive approximation, and include a blocked variant that improves locality by confining probes to one block per epoch. Experiments cover 225 synthetic streaming configurations and 45 configurations from a timestamp-ordered web-server access-log stream. At 14 bits per live item, the guarded epoch filter reduces median synthetic false positives from 0.191 for a four-bit counting Bloom baseline to 0.02225 while preserving zero measured live-key false negatives. The method is not a replacement for exact deletion; it targets systems where bounded stale positives are acceptable but false negatives inside the live window are not.
From: Levent Sarioglu [view email]
[v1]
Wed, 17 Jun 2026 15:45:59 UTC (2,249 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。