More Web Proxy on the site http://driver.im/

research-article

Cache-, hash-, and space-efficient bloom filters

Authors:

Johannes SinglerAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 14

Article No.: 4, Pages 4.4 - 4.18

https://doi.org/10.1145/1498698.1594230

Published: 05 January 2010 Publication History

Abstract

A Bloom filter is a very compact data structure that supports approximate membership queries on a set, allowing false positives.

We propose several new variants of Bloom filters and replacements with similar functionality. All of them have a better cache-efficiency and need less hash bits than regular Bloom filters. Some use SIMD functionality, while the others provide an even better space efficiency. As a consequence, we get a more flexible trade-off between false-positive rate, space-efficiency, cache-efficiency, hash-efficiency, and computational effort. We analyze the efficiency of Bloom filters and the proposed replacements in detail, in terms of the false-positive rate, the number of expected cache-misses, and the number of required hash bits. We also describe and experimentally evaluate the performance of highly tuned implementations. For many settings, our alternatives perform better than the methods proposed so far.

References

[1]

Bloom, B. H. 1970. Space-time trade-offs in hash coding with allowable errors. Commun. ACM 13, 7.

Digital Library

[2]

Broder, A. and Mitzenmacher, M. 2004. Network applications of bloom filters: A survey. Internet Math. 1, 4.

[3]

Buhrman, H., Miltersen, P. B., Radhakrishnan, J., and Venkatesh, S. 2002. Are bit-vectors optimal&quest; SIAM J. Comput 31, 6, 1723--1744.

Digital Library

[4]

Cleary, J. G. 1984. Compact hash tables using bidirectional linear probing. IEEE Trans. Comput. 33, 9, 828--834.

Digital Library

[5]

Dillinger, P. C. and Manolios, P. 2004a. Bloom filters in probabilistic verification. In Proceedings of the 6th International Formal Methods in Computer-Aided Design (FMCAD'04). Springer, Berlin, 367--381.

[6]

Dillinger, P. C. and Manolios, P. 2004b. Fast and accurate bit-state verification for SPIN. In Proceedings of the 11th International SPIN Workshop. Springer, Berlin, 57--75.

[7]

Fan, L., Cao, P., Almeida, J. M., and Broder, A. Z. 2000. Summary cache: A scalable wide-area web cache sharing protocol. IEEE/ACM TON 8, 3, 281--293.

Digital Library

[8]

Kirsch, A. and Mitzenmacher, M. 2006. Less hashing, same performance: Building a better Bloom filter. In Proceedings of the 14th European Symposium (ESA'06). Springer, Berlin, 456--467.

Digital Library

[9]

Lumetta, S. and Mitzenmacher, M. 2006. Using the power of two choices to improve bloom filters. http://www.eecs.harvard.edu/~michaelm/postscripts/bftwo.ps.

[10]

Manber, U. and Wu, S. 1994. An algorithm for approximate membership checking with application to password security. Inform. Process. Lett. 50, 4 (25), 191--197.

Digital Library

[11]

Mitzenmacher, M. 2001. Compressed Bloom filters. In PODC 2001. 144--150.

Digital Library

[12]

Moffat, A. and Turpin, A. 2002. Compression and Coding Algorithms. Kluwer.

Digital Library

[13]

Pagh, A., Pagh, R., and Rao, S. S. 2005. An optimal Bloom filter replacement. In Proceedings of the 16th Annual Symposium on Discrete Algorithms (SODA'05). ACM, New York, 823--829.

Digital Library

[14]

Patrascu, M. 2008. Succincter. In Proceedings of the 49th Annual IEEE Symposium on Foundation of Computer Science (FOCS'08). IEEE, Los Alamitos, CA, 305--313.

Digital Library

[15]

Sanders, P. and Transier, F. 2007. Intersection in integer inverted indices. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics, Philadephia.

Cited By

Mersy GWang ZSintos SKrishnan S(2024)Optimizing Collections of Bloom Filters within a Space BudgetProceedings of the VLDB Endowment10.14778/3681954.368202017:11(3551-3564)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682020
Birler ASchmidt TFent PNeumann T(2024)Simple, Efficient, and Robust Hash Tables for Join ProcessingProceedings of the 20th International Workshop on Data Management on New Hardware10.1145/3662010.3663442(1-9)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3662010.3663442
Zheng HLi YXiong FLi XZou LShi PQin Z(2024)Vertex Encoding for Edge Nonexistence Determination With SIMD AccelerationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.335091936:7(3600-3614)Online publication date: Jul-2024
https://doi.org/10.1109/TKDE.2024.3350919
Show More Cited By

Index Terms

Cache-, hash-, and space-efficient bloom filters
1. Information systems
  1. Information storage systems
    1. Record storage systems
      1. Record storage alternatives
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching

Recommendations

Software-Based Cache Coherence with Hardware-Assisted Selective Self-Invalidations Using Bloom Filters

Implementing shared memory consistency models on top of hardware caches gives rise to the well-known cache coherence problem. The standard solution involves implementing coherence protocols in hardware, an approach with some design complexity, hardware ...
Cache-, hash- and space-efficient bloom filters
WEA'07: Proceedings of the 6th international conference on Experimental algorithms

A Bloom filter is a very compact data structure that supports approximate membership queries on a set, allowing false positives.

We propose several new variants of Bloom filters and replacements with similar functionality. All of them have a better ...
Compression-Based Program Characterization for Improving Cache Memory Performance

It is well known that compression and prediction are interrelated in that high compression implies good predictability, and vice versa. We use this correlation to find predictable properties of program behavior and apply them to appropriate cache ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics

ACM Journal of Experimental Algorithmics Volume 14, Issue

2009

613 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/1498698

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 January 2010

Accepted: 01 July 2009

Received: 01 January 2009

Published in JEA Volume 14

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Deutsche Forschungsgemeinschaft

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
817
Total Downloads

Downloads (Last 12 months)52
Downloads (Last 6 weeks)7

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mersy GWang ZSintos SKrishnan S(2024)Optimizing Collections of Bloom Filters within a Space BudgetProceedings of the VLDB Endowment10.14778/3681954.368202017:11(3551-3564)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682020
Birler ASchmidt TFent PNeumann T(2024)Simple, Efficient, and Robust Hash Tables for Join ProcessingProceedings of the 20th International Workshop on Data Management on New Hardware10.1145/3662010.3663442(1-9)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3662010.3663442
Zheng HLi YXiong FLi XZou LShi PQin Z(2024)Vertex Encoding for Edge Nonexistence Determination With SIMD AccelerationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.335091936:7(3600-3614)Online publication date: Jul-2024
https://doi.org/10.1109/TKDE.2024.3350919
Reviriego PSánchez-Macian ADillinger PWalzer S(2024)On the Privacy of Multi-Versioned Approximate Membership Check FiltersIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.329896721:4(1981-1993)Online publication date: Jul-2024
https://doi.org/10.1109/TDSC.2023.3298967
Gessert FWingerath WRitter NGessert FWingerath WRitter N(2024)Caching in Forschung und IndustrieSchnelles und skalierbares Cloud-Datenmanagement10.1007/978-3-031-54388-3_5(91-140)Online publication date: 3-May-2024
https://doi.org/10.1007/978-3-031-54388-3_5
Dayan NBercea IReviriego PPagh R(2023)InfiniFilter: Expanding Filters to Infinity and BeyondProceedings of the ACM on Management of Data10.1145/35892851:2(1-27)Online publication date: 20-Jun-2023
https://doi.org/10.1145/3589285
Yao JMeng XZheng YWang C(2023)Privacy-Preserving Content-Based Similarity Detection Over in-the-Cloud MiddleboxesIEEE Transactions on Cloud Computing10.1109/TCC.2022.316932911:2(1854-1870)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TCC.2022.3169329
Almeida P(2023)A Case for Partitioned Bloom FiltersIEEE Transactions on Computers10.1109/TC.2022.321899572:6(1681-1691)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1109/TC.2022.3218995
Sanders PUhl T(2023)Engineering a Distributed-Memory Triangle Counting Algorithm2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS54959.2023.00076(702-712)Online publication date: May-2023
https://doi.org/10.1109/IPDPS54959.2023.00076
Sarkar SDayan NAthanassoulis M(2023)The LSM Design Space and its Read Optimizations2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00273(3578-3584)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00273
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents