Sliding Bloom Filters

DOI10.1007/978-3-642-45030-3_48MaRDI QIDQ2872115zbMATHOpenAlexFDO

Authors Moni Naor, Eylon Yogev

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.5872

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: A Bloom filter is a method for reducing the space (memory) required for representing a set by allowing a small error probability. In this paper we consider a emph{Sliding Bloom Filter}: a data structure that, given a stream of elements, supports membership queries of the set of the last $n$ elements (a sliding window), while allowing a small error probability. We formally define the data structure and its relevant parameters and analyze the time and memory requirements needed to achieve them. We give a low space construction that runs in O(1) time per update with high probability (that is, for all sequences with high probability all operations take constant time) and provide an almost matching lower bound on the space that shows that our construction has the best possible space consumption up to an additive lower order term.

Recommendations

• Tight bounds for sliding Bloom filters
• Scalable Bloom filters
• Bloomier Filters: A Second Look
• An optimal bloom filter replacement
• Distance-Sensitive Bloom Filters
• Compressed Bloom filters
• On the analysis of Bloom filters
• Optimizing data popularity conscious Bloom filters
• M-balance matrix Bloom filter
• Formal Methods in Computer-Aided Design

Cited in

(5)

• Give me some slack: efficient network measurements
• Tight bounds for sliding Bloom filters
• Give me some slack: efficient network measurements
• Succinct summing over sliding windows
• Inferring insertion times and optimizing error penalties in time-decaying Bloom filters

This page was built for publication: Sliding Bloom Filters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2872115)