article

Building high accuracy bloom filters using partitioned hashing

Authors:

Fang Hao,

Murali Kodialam,

T. V. LakshmanAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 35, Issue 1

Pages 277 - 288

https://doi.org/10.1145/1269899.1254916

Published: 12 June 2007 Publication History

Get Access

Abstract

The growing importance of operations such as packet-content inspection, packet classification based on non-IP headers, maintaining flow-state, etc. has led to increased interest in the networking applications of Bloom filters. This is because Bloom filters provide a relatively easy method for hardware implementation of set-membership queries. However, the tradeoff is that Bloom filters only provide a probabilistic test and membership queries can result in false positives. Ideally, we would like this false positive probability to be very low. The main contribution of this paper is a method for significantly reducing this false positive probability in comparison to existing schemes. This is done by developing a partitioned hashing method which results in a choice of hash functions that set far fewer bits in the Bloom filter bit vector than would be the case otherwise. This lower fill factor of the bit vector translates to a much lower false positive probability. We show experimentally that this improved choice can result in as much as a ten-fold increase in accuracy over standard Bloom filters. We also show that the scheme performs much better than other proposed schemes for improving Bloom filters.

References

[1]

B. H. Bloom, "Space/time tradeoffs in hash coding with allowable errors", Communications of the ACM 13:7 (1970), 422--426.

Digital Library

Google Scholar

[2]

A. Kirsch and M. Mitzenmacher, "Less hashing, same performance: building a better Bloom filter", ESA 2006.

Digital Library

Google Scholar

[3]

S. Lumetta and M. Mitzenmacher, "Using the power of two choices to improve Bloom filters", Preprint version available at http://www.eecs.harvard.edu/~michaelm.

Google Scholar

[4]

A. Broder and M. Mitzenmacher, "Network applications fo Bloom filters: a survey", Internet Mathematics, vol. 1. no. 4, pp. 485--509, 2005.

Google Scholar

[5]

R. Motwani and P. Raghavan, "Randomized algorithms", Cambridge University Press, August, 1995.

Digital Library

Google Scholar

[6]

Robert Sedgewick, "Algorithms in C", Addison-Wesley Professional, August, 2001.

Google Scholar

[7]

A. Ostlin and R. Pagh, "Uniform hashing in constant time and linear space", Proceedings of STOC 2003, ACM.

Digital Library

Google Scholar

[8]

A. Pagh, R. Pagh, and S. Rao, "An optimal Bloom filter replacement", SODA 2005.

Digital Library

Google Scholar

[9]

B. Chazelle, J. Kilian, R. Rubinfeld, and A. Tal, "The Bloomier filter: an efficient data structure for static support lookup tables", SODA 2004.

Digital Library

Google Scholar

[10]

C. Estan and G. Varghese, "New directions in traffic measurement and accounting", Proceedings of ACM SIGCOMM Conference, 2002.

Digital Library

Google Scholar

[11]

L. Fan, P. Cao, J. Almeida, and A. Z. Broder, "Summary cache: a scalable wide-area web cache sharing protocol", IEEE/ACM Transactions on Networking 8:3 (2000), 281--293.

Digital Library

Google Scholar

[12]

E. H. Spafford, "Opus: preventing weak password choices", Computer and Security 11 (1992), 273--278.

Digital Library

Google Scholar

[13]

U. Manber and S. Wu, "An algorithm for approximate membership checking with application to password security", Information Processing Letters 50 (1994), 19--197.

Digital Library

Google Scholar

[14]

F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese, "Beyond Bloom filters: from approximate membership checks to approximate state machines", Proceedings of ACM SIGCOMM 2006.

Digital Library

Google Scholar

Cited By

View all

Hua YLiu XHua YLiu X(2019)Locality-Sensitive Bloom Filter for Approximate Membership QuerySearchable Storage in Cloud Computing10.1007/978-981-13-2721-6_5(99-127)Online publication date: 9-Feb-2019
https://doi.org/10.1007/978-981-13-2721-6_5
Ma XXu LXu L(2019)Blockchain Retrieval Model Based on Elastic Bloom FilterWeb Information Systems and Applications10.1007/978-3-030-30952-7_53(527-538)Online publication date: 20-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-30952-7_53
Ameri MDelavar MMohajeri J(2019)Provably secure and efficient PUF‐based broadcast authentication schemes for smart grid applicationsInternational Journal of Communication Systems10.1002/dac.393532:8Online publication date: 5-Mar-2019
https://doi.org/10.1002/dac.3935
Show More Cited By

Index Terms

Building high accuracy bloom filters using partitioned hashing
1. Hardware
  1. Communication hardware, interfaces and storage
2. Networks

Recommendations

Building high accuracy bloom filters using partitioned hashing
SIGMETRICS '07: Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

The growing importance of operations such as packet-content inspection, packet classification based on non-IP headers, maintaining flow-state, etc. has led to increased interest in the networking applications of Bloom filters. This is because Bloom ...
False Negative Problem of Counting Bloom Filter

Bloom filter is effective, space-efficient data structure for concisely representing a data set and supporting approximate membership queries. Traditionally, researchers often believe that it is possible that a Bloom filter returns a false positive, but ...
The Bloom paradox: when not to use a Bloom filter

In this paper, we uncover the Bloom paradox in Bloom Filters: Sometimes, the Bloom Filter is harmful and should not be queried. We first analyze conditions under which the Bloom paradox occurs in a Bloom Filter and demonstrate that it depends on the a ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 35, Issue 1

SIGMETRICS '07 Conference Proceedings

June 2007

382 pages

ISSN:0163-5999

DOI:10.1145/1269899

Issue’s Table of Contents

SIGMETRICS '07: Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
June 2007
398 pages
ISBN:9781595936394
DOI:10.1145/1254882
General Chair:
Leana Golubchik
University of Southern California, USA
,
Program Chairs:
Mostafa Ammar
Georgia Institute of Technology, USA
,
Mor Harchol-Balter
Carnegie Mellon University, USA

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: 12 June 2007

Published in SIGMETRICS Volume 35, Issue 1

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
1,550
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hua YLiu XHua YLiu X(2019)Locality-Sensitive Bloom Filter for Approximate Membership QuerySearchable Storage in Cloud Computing10.1007/978-981-13-2721-6_5(99-127)Online publication date: 9-Feb-2019
https://doi.org/10.1007/978-981-13-2721-6_5
Ma XXu LXu L(2019)Blockchain Retrieval Model Based on Elastic Bloom FilterWeb Information Systems and Applications10.1007/978-3-030-30952-7_53(527-538)Online publication date: 20-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-30952-7_53
Ameri MDelavar MMohajeri J(2019)Provably secure and efficient PUF‐based broadcast authentication schemes for smart grid applicationsInternational Journal of Communication Systems10.1002/dac.393532:8Online publication date: 5-Mar-2019
https://doi.org/10.1002/dac.3935
Liu YGe XDu DHuang X(2016)Par-BF: A parallel partitioned Bloom filter for dynamic data setsThe International Journal of High Performance Computing Applications10.1177/109434201561845230:3(259-275)Online publication date: 28-Jul-2016
https://doi.org/10.1177/1094342015618452
Yang XVernitski ACarrea L(2016)An approximate dynamic programming approach for improving accuracy of lossy data compression by Bloom filtersEuropean Journal of Operational Research10.1016/j.ejor.2016.01.042252:3(985-994)Online publication date: Aug-2016
https://doi.org/10.1016/j.ejor.2016.01.042
Liu XQi HLi KStojmenovic ILiu AShen YQu WXue W(2015)Sampling Bloom Filter-Based Detection of Unknown RFID TagsIEEE Transactions on Communications10.1109/TCOMM.2015.240266063:4(1432-1442)Online publication date: Apr-2015
https://doi.org/10.1109/TCOMM.2015.2402660
Liu XLi KMin GShen YLiu AQu W(2015)Completely Pinpointing the Missing RFID Tags in a Time-Efficient WayIEEE Transactions on Computers10.1109/TC.2013.19764:1(87-96)Online publication date: Jan-2015
https://doi.org/10.1109/TC.2013.197
Lu JYang TWang YDai HJin LSong HLiu B(2015)One-hashing bloom filter2015 IEEE 23rd International Symposium on Quality of Service (IWQoS)10.1109/IWQoS.2015.7404748(289-298)Online publication date: Jun-2015
https://doi.org/10.1109/IWQoS.2015.7404748
Bremler-Barr ADavid SHarchol YHay D(2015)Leveraging traffic repetitions for high-speed deep packet inspection2015 IEEE Conference on Computer Communications (INFOCOM)10.1109/INFOCOM.2015.7218648(2578-2586)Online publication date: Apr-2015
https://doi.org/10.1109/INFOCOM.2015.7218648
Saravanan KSenthilkumar A(2015)An Insight Review on Bloom Filter and Its Variants with Applications: An Emerging Hash Based Membership Querying TechniqueJournal of Discrete Mathematical Sciences and Cryptography10.1080/09720529.2014.93212918:3(247-263)Online publication date: 2-Jun-2015
https://doi.org/10.1080/09720529.2014.932129
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 Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations