article

Free access

A second look at bloom filters

Author:

James K. MullinAuthors Info & Claims

Communications of the ACM, Volume 26, Issue 8

Pages 570 - 571

https://doi.org/10.1145/358161.358167

Published: 01 August 1983 Publication History

PDF eReader

Abstract

This note deals with a paper by Gremillion demonstrating the simulation approach to the design of a Bloom filter. It is shown that an analytical approach can yield insights into competing filter design and give expected values for the goodness-of-hash transformations not available with simulation. On the other hand, simulation gives insight into what can be expected with available hash transformation not available from an analytic approach.

References

[1]

Bloom, B.H. Space/time tradeoffs in hash coding with allowable errors. Comm. ACM 13, 7 (July 1970), 422--426.

Digital Library

Google Scholar

[2]

Gremillion, L.L. Designing a Bloom Filter for differential file access. Comm. ACM 25, 9 (Sept. 1982). 600-604.

Digital Library

Google Scholar

[3]

Lum, V.Y., Yuen, P.S.T. and Dodd, M. Key to address transformation techniques: A fundamental performance study on large existing formatted files. Comm. ACM 14, 4 (April 1971), 228-239.

Digital Library

Google Scholar

Cited By

View all

Lu YCai BTang XLiu LDu JYu SAtiquzzaman MDustdar S(2024)Tree-ORAP: A Tree-Based Oblivious Random-Access Protocol for Privacy-Protected BlockchainIEEE Transactions on Services Computing10.1109/TSC.2023.334758917:3(1252-1264)Online publication date: May-2024
https://doi.org/10.1109/TSC.2023.3347589
Li YMa JMiao YWang XLu RZhang W(2024)Secure and Efficient Bloom-Filter-Based Image Search in Cloud-Based Internet of ThingsIEEE Internet of Things Journal10.1109/JIOT.2023.330196911:3(5024-5035)Online publication date: 1-Feb-2024
https://doi.org/10.1109/JIOT.2023.3301969
Wang ZLuo T(2024)A Scalable, Fault Resilient and Balanced Storage Architecture for Cyber-Physical Systems2024 IEEE 19th Conference on Industrial Electronics and Applications (ICIEA)10.1109/ICIEA61579.2024.10665062(1-6)Online publication date: 5-Aug-2024
https://doi.org/10.1109/ICIEA61579.2024.10665062
Show More Cited By

Index Terms

A second look at bloom filters
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data access methods
  2. Information storage systems
    1. Record storage systems
      1. Record storage alternatives
        Hashed file organization
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Compressed bloom filters
PODC '01: Proceedings of the twentieth annual ACM symposium on Principles of distributed computing

A Bloom filter is a simple space-efficient randomized data structure for representing a set in order to support membership queries. Although Bloom filters allow false positives, for many applications the space savings outweigh this draw-back when the ...
The Angular Rate Matching of Transfer Alignment by Using H8 Filter
MACE '12: Proceedings of the 2012 Third International Conference on Mechanic Automation and Control Engineering

The filter is adopted in the transfer alignment (TA) scheme of the angular rate matching. The various stages of disturbance in measurements are completely unknown, the TA performance of filter is compared with that of Kalman filter. Results of ...
Power Measurement Based on Half-Band Filters
ICEICE '12: Proceedings of the 2012 Second International Conference on Electric Information and Control Engineering - Volume 01

The half-band filters are widely used in signal process owe to better amplitude-frequence performance. This paper discusseed the relationships between orthogonal wavelet and half-band filters, together with simulations, a proposed power measurement ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 26, Issue 8

Aug. 1983

50 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/358161

Editor:
Peter J. Danning
NASA Ames Research Center, Moffett Field, CA

Issue’s Table of Contents

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: 01 August 1983

Published in CACM Volume 26, Issue 8

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

90
Total Citations
View Citations
1,582
Total Downloads

Downloads (Last 12 months)127
Downloads (Last 6 weeks)14

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lu YCai BTang XLiu LDu JYu SAtiquzzaman MDustdar S(2024)Tree-ORAP: A Tree-Based Oblivious Random-Access Protocol for Privacy-Protected BlockchainIEEE Transactions on Services Computing10.1109/TSC.2023.334758917:3(1252-1264)Online publication date: May-2024
https://doi.org/10.1109/TSC.2023.3347589
Li YMa JMiao YWang XLu RZhang W(2024)Secure and Efficient Bloom-Filter-Based Image Search in Cloud-Based Internet of ThingsIEEE Internet of Things Journal10.1109/JIOT.2023.330196911:3(5024-5035)Online publication date: 1-Feb-2024
https://doi.org/10.1109/JIOT.2023.3301969
Wang ZLuo T(2024)A Scalable, Fault Resilient and Balanced Storage Architecture for Cyber-Physical Systems2024 IEEE 19th Conference on Industrial Electronics and Applications (ICIEA)10.1109/ICIEA61579.2024.10665062(1-6)Online publication date: 5-Aug-2024
https://doi.org/10.1109/ICIEA61579.2024.10665062
Lucas OGeorge A(2024)Leveraging HBM2 for Accelerating k-mer Counting with oneAPI on FPGAs2024 34th International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL64840.2024.00022(92-99)Online publication date: 2-Sep-2024
https://doi.org/10.1109/FPL64840.2024.00022
Hadian Dehkordi MMashhadi SFarahi SNoorallahzadeh M(2024)Verifiable Changeable Threshold Secret Image Sharing Scheme Based on LWE ProblemWireless Personal Communications: An International Journal10.1007/s11277-024-11454-z137:2(1099-1118)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11277-024-11454-z
Xu YShao JSlaats TDüdder B(2023)MWPoW+: A Strong Consensus Protocol for Intra-Shard Consensus in Blockchain ShardingACM Transactions on Internet Technology10.1145/358402023:2(1-27)Online publication date: 18-May-2023
https://dl.acm.org/doi/10.1145/3584020
Fernandes PBaquero CGonzalez Boix ESutra P(2023)Probabilistic Causal Contexts for Scalable CRDTsProceedings of the 10th Workshop on Principles and Practice of Consistency for Distributed Data10.1145/3578358.3591331(1-8)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3578358.3591331
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
Dehkordi MFarahi SMashhadi S(2023)LWE‐based verifiable essential secret image sharing scheme ((t,s,k,n)$( {t,s,k,n} )$ ‐ VESIS)IET Image Processing10.1049/ipr2.13006Online publication date: 8-Dec-2023
https://doi.org/10.1049/ipr2.13006
Hadian Dehkordi MFarahi SMashhadi S(2023)A verifiable essential secret image sharing scheme based on HLRs (VESIS‐(t, s, k, n))CAAI Transactions on Intelligence Technology10.1049/cit2.122719:2(388-410)Online publication date: 20-Oct-2023
https://dl.acm.org/doi/10.1049/cit2.12271
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Abstract

References

Cited By

Index Terms

Recommendations

Compressed bloom filters

The Angular Rate Matching of Transfer Alignment by Using H8 Filter

Power Measurement Based on Half-Band Filters

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations