Article

An optimal Bloom filter replacement

Authors:

S. Srinivasa RaoAuthors Info & Claims

SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 823 - 829

Published: 23 January 2005 Publication History

Abstract

This paper considers space-efficient data structures for storing an approximation S' to a set S such that S ⊆ S' and any element not in S belongs to S' with probability at most ∈. The Bloom filter data structure, solving this problem, has found widespread use. Our main result is a new RAM data structure that improves Bloom filters in several ways:• The time for looking up an element in S' is O(1), independent of ∈.• The space usage is within a lower order term of the lower bound.• The data structure uses explicit hash function families.• The data structure supports insertions and deletions on S in amortized expected constant time.The main technical ingredient is a succinct representation of dynamic multisets. We also consider three recent generalizations of Bloom filters.

References

[1]

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

Digital Library

[2]

A. Z. Broder and M. Mitzenmacher. Network applications of Bloom filters: A survey. In Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing, pages 636--646. ACM Press, 2002.]]

[3]

A. Brodnik and J. I. Munro. Membership in constant time and almost-minimum space. SIAM J. Comput., 28(5):1627--1640, 1999.]]

Digital Library

[4]

J. L. Carter and M. N. Wegman. Universal classes of hash functions. J. Comput. System Sci., 18(2):143--154, 1979.]]

[5]

L. Carter, R. Floyd, J. Gill, G. Markowsky, and M. Wegman. Exact and approximate membership testers. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC '78), pages 59--65. ACM Press, 1978.]]

Digital Library

[6]

B. Chazelle, J. Kilian, R. Rubinfeld, and A. Tal. The Bloomier filter: An efficient data structure for static support lookup tables. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '04), pages 30--39. ACM Press, 2004.]]

Digital Library

[7]

M. J. Clancy and D. E. Knuth. A programming and problem-solving seminar. Technical Report CS-TR-77-606, Stanford University, Department of Computer Science, 1977.]]

Digital Library

[8]

J. G. Cleary. Compact hash tables using bidirectional linear probing. IEEE Transactions on Computers, C-33(9):828--834, Sept. 1984.]]

[9]

S. Cohen and Y. Matias. Spectral Bloom filters. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data 2003, pages 241--252. ACM Press, 2003.]]

Digital Library

[10]

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):281--293, 2000.]]

Digital Library

[11]

T. Hagerup and T. Tholey. Efficient minimal perfect hashing in nearly minimal space. In Proceedings of the 18th Symposium on Theoretical Aspects of Computer Science (STACS '01), volume 2010 of Lecture Notes in Computer Science, pages 317--326. Springer-Verlag, 2001.]]

Digital Library

[12]

M. Mitzenmacher. Compressed Bloom filters. IEEE/ACM Transactions on Networking, 10(5):604--612, 2002.]]

Digital Library

[13]

C. W. Mortensen, R. Pagh, and M. Pătraşcu. On dynamic range reporting in one dimension. Manuscript, 2004.]]

[14]

A. Östlin and R. Pagh. Uniform hashing in constant time and linear space. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC '03), pages 622--628. ACM Press, 2003.]]

Digital Library

[15]

R. Pagh. Dispersing Hash Functions. In Proceedings of the 4th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM '00), volume 8 of Proceedings in Informatics, pages 53--67. Carleton Scientific, 2000.]]

[16]

R. Pagh. Low redundancy in static dictionaries with constant query time. SIAM J. Comput., 31(2):353--363, 2001.]]

Digital Library

[17]

R. Pagh and F. F. Rodler. Lossy dictionaries. In Proceedings of the 9th European Symposium on Algorithms (ESA '01), volume 2161 of Lecture Notes in Computer Science, pages 300--311. Springer-Verlag, 2001.]]

Digital Library

[18]

R. Raman, V. Raman, and S. S. Rao. Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '02), pages 233--242. ACM Press, 2002.]]

Digital Library

[19]

R. Raman and S. S. Rao. Succinct dynamic dictionaries and trees. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP '03), volume 2719 of Lecture Notes in Computer Science, pages 357--368. Springer-Verlag, 2003.]]

Digital Library

Cited By

Wen RMcCoy HTench DTagliavini GBender MConway AFarach-Colton MJohnson RPandey P(2024)Adaptive Quotient FiltersProceedings of the ACM on Management of Data10.1145/36771282:4(1-28)Online publication date: 30-Sep-2024
https://dl.acm.org/doi/10.1145/3677128
Pandey PFarach-Colton MDayan NZhang HBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)Beyond Bloom: A Tutorial on Future Feature-Rich FiltersCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3654681(636-644)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3654681
Roy IAgarwal RChakrabarti SDasgupta ADe AOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Locality sensitive hashing in fourier frequency domain for soft set containment searchProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668581(56352-56383)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668581
Show More Cited By

An optimal Bloom filter replacement

Recommendations

Application and Research on Weighted Bloom Filter and Bloom Filter in Web Cache
WMWA '09: Proceedings of the 2009 Second Pacific-Asia Conference on Web Mining and Web-based Application

A Bloom filter is a simple space-efficient randomized data structure for representing a set in order to support membership queries. Bloom filters and their generalizations, weighted Bloom filters and compressed Bloom filters have been suggested as a ...
Evaluation of the Structured Bloom Filter
CISIS '10: Proceedings of the 2010 International Conference on Complex, Intelligent and Software Intensive Systems

A Bloom filter offers a simple space-efficient randomized data structure for representing a set in order to support membership queries. The Bloom filter has become attractive as one of the methods of looking up data in the distributed system. Since two ...
K-Divided Bloom Filter Algorithm and Its Analysis
FGCN '07: Proceedings of the Future Generation Communication and Networking - Volume 01

By using a bit vector and a set of hash functions to represent data set, Bloom Filter can query a given data effectively. Bloom Filter can be used to determine an element belongs to data set or not. Split Bloom Filter is amelioration to the Bloom Filter, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms

January 2005

1205 pages

ISBN:0898715857

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 23 January 2005

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
1,467
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)1

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wen RMcCoy HTench DTagliavini GBender MConway AFarach-Colton MJohnson RPandey P(2024)Adaptive Quotient FiltersProceedings of the ACM on Management of Data10.1145/36771282:4(1-28)Online publication date: 30-Sep-2024
https://dl.acm.org/doi/10.1145/3677128
Pandey PFarach-Colton MDayan NZhang HBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)Beyond Bloom: A Tutorial on Future Feature-Rich FiltersCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3654681(636-644)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3654681
Roy IAgarwal RChakrabarti SDasgupta ADe AOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Locality sensitive hashing in fourier frequency domain for soft set containment searchProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668581(56352-56383)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668581
Li HWang LChen QJi JWu YZhao YYang TAkella A(2023)ChainedFilter: Combining Membership Filters by Chain RuleProceedings of the ACM on Management of Data10.1145/36267211:4(1-27)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626721
McCoy HHofmeyr SYelick KPandey PDehnavi MKulkarni MKrishnamoorthy S(2023)High-Performance Filters for GPUsProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577507(160-173)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577507
Thomas ADasgupta SRosing T(2022)A Theoretical Perspective on Hyperdimensional ComputingJournal of Artificial Intelligence Research10.1613/jair.1.1266472(215-249)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1613/jair.1.12664
Modi ARajan KThimmaiah SJain PMann SAgarwal AShetty AI SGosalia ASarthi P(2022)New query optimization techniques in the Spark engine of Azure synapseProceedings of the VLDB Endowment10.14778/3503585.350360115:4(936-948)Online publication date: 14-Apr-2022
https://dl.acm.org/doi/10.14778/3503585.3503601
Bender MFarach-Colton MKuszmaul JKuszmaul WLiu MLeonardi SGupta A(2022)On the optimal time/space tradeoff for hash tablesProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3519969(1284-1297)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3519969
Dayan NTwitto MLi GLi ZIdreos SSrivastava D(2021)Chucky: A Succinct Cuckoo Filter for LSM-TreeProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3457273(365-378)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3457273
Pandey PConway ADurie JBender MFarach-Colton MJohnson RLi GLi ZIdreos SSrivastava D(2021)Vector Quotient FiltersProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3452841(1386-1399)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3452841
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.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents