Constructions and applications for accurate counting of the bloom filter false positive free zone

Ori Rottenstreich, Pedro Reviriego, Ely Porat, S. Muthukrishnan

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    Bloom filters are used in many networking applications to answer set membership queries at low cost but suffer from false positives. We study Bloom filter constructions that when representing a set of size up to d taken from a finite universe of size n, completely avoid false positives. We suggest memory-efficient Bloom filters constructions with a false positive free zone to allow representations of larger sets through linear memory dependency in the set size. Our first construction relies on Orthogonal Latin Square (OLS) codes and the second relies on the representation of elements through values of polynomials defined modulo primes. Beyond Bloom filters supporting set membership, we also consider sketches allowing a more general functionality such as flow size estimation. In particular, we show the applicability of the false positive free zone for accurate size estimation in the famous Count-Min sketch. We compare the new constructions to existing approaches through analytical and experimental evaluations for showing their superiority.

    Original languageEnglish (US)
    Title of host publicationSOSR 2020 - Proceedings of the 2020 Symposium on SDN Research
    PublisherAssociation for Computing Machinery, Inc
    Pages135-145
    Number of pages11
    ISBN (Electronic)9781450371018
    DOIs
    StatePublished - Mar 3 2020
    Event2020 Symposium on SDN Research, SOSR 2020 - San Jose, United States
    Duration: Mar 3 2020 → …

    Publication series

    NameSOSR 2020 - Proceedings of the 2020 Symposium on SDN Research

    Conference

    Conference2020 Symposium on SDN Research, SOSR 2020
    CountryUnited States
    CitySan Jose
    Period3/3/20 → …

    Keywords

    • Bloom filter
    • Count-Min Sketch
    • Flow size estimation
    • Measurement

    ASJC Scopus subject areas

    • Computer Networks and Communications
    • Software

    Fingerprint Dive into the research topics of 'Constructions and applications for accurate counting of the bloom filter false positive free zone'. Together they form a unique fingerprint.

  • Cite this

    Rottenstreich, O., Reviriego, P., Porat, E., & Muthukrishnan, S. (2020). Constructions and applications for accurate counting of the bloom filter false positive free zone. In SOSR 2020 - Proceedings of the 2020 Symposium on SDN Research (pp. 135-145). (SOSR 2020 - Proceedings of the 2020 Symposium on SDN Research). Association for Computing Machinery, Inc. https://doi.org/10.1145/3373360.3380845