Tight bounds for sliding Bloom filters

DOI10.1007/S00453-015-0007-9MaRDI QIDQ5963376zbMATH OpenOpenAlexFDO

Authors Moni Naor, Eylon Yogev

Publication date 19 February 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-015-0007-9

zbMATH Keywords

data structureslower boundsBloom filterstreaming algorithmshash tables

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Sliding Bloom Filters
• An optimal bloom filter replacement
• Bloomier Filters: A Second Look
• Cache-, hash-, and space-efficient bloom filters
• Distance-Sensitive Bloom Filters

Cites work

• A space lower bound for dynamic approximate membership data structures
• An optimal bloom filter replacement
• Exact and approximate membership testers
• Maintaining Stream Statistics over Sliding Windows
• Network Applications of Bloom Filters: A Survey
• Space/time trade-offs in hash coding with allowable errors
• Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Universal classes of hash functions

Cited in

(5)

• Encapsulated search index: public-key, sub-linear, distributed, and delegatable
• scientific article; zbMATH DE number 7765407 (Why is no real title available?)
• Sliding Bloom Filters
• A space lower bound for dynamic approximate membership data structures
• Inferring insertion times and optimizing error penalties in time-decaying Bloom filters

This page was built for publication: Tight bounds for sliding Bloom filters

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