Tight bounds for sliding Bloom filters

DOI10.1007/S00453-015-0007-9zbMATH Open1331.68064OpenAlexW2108423974MaRDI QIDQ5963376FDOQ5963376

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

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

zbMATH Keywords

data structureslower boundsBloom filterstreaming algorithmshash tables

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

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

Cited In (6)

• Encapsulated search index: public-key, sub-linear, distributed, and delegatable
• Title not available (Why is that?)
• 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
• Bloom filters in adversarial environments

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)