Sliding Bloom Filters

DOI10.1007/978-3-642-45030-3_48zbMATH Open1329.68088arXiv1304.5872OpenAlexW2143383498MaRDI QIDQ2872115FDOQ2872115

Authors: Moni Naor, Eylon Yogev 

Publication date: 14 January 2014

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

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.

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

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

Mathematics Subject Classification ID

Data structures (68P05)

Cited In (4)

• Succinct summing over sliding windows
• Bloom Filters in Adversarial Environments
• Title not available (Why is that?)
• Give me some slack: efficient network measurements

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)