Space/time trade-offs in hash coding with allowable errors
Open accessThe DOI matches its Crossref record.
Abstract
In this paper trade-offs among certain computational factors in hash coding are analyzed. The paradigm problem considered is that of testing a series of messages one-by-one for membership in a given set of messages. Two new hash-coding methods are examined and compared with a particular conventional hash-coding method. The computational factors considered are the size of the hash area (space), the time required to identify a message as a nonmember of the given set (reject time), and an allowable error frequency. The new methods are intended to reduce the amount of space required to contain the hash-coded information from that associated with conventional methods. The reduction in space is accomplished by exploiting the possibility that a small fraction of errors of commission may be tolerable in some applications, in particular, applications in which a large amount of data is involved and a core resident hash area is consequently not feasible using conventional methods. In such applications, it is envisaged that overall performance could be improved by using a smaller core resident hash area in conjunction with the new methods and, when necessary, by using some secondary and perhaps time-consuming test to “catch” the small fraction of errors associated with the new methods. An example is discussed which illustrates possible areas of application for the new methods. Analysis of the paradigm problem demonstrates that allowing a small number of test messages to be falsely identified as members of the given set will permit a much smaller hash area to be used without increasing reject time.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
No references could be resolved yet.
Research works printed but not linked: 3
- 10.1145/363744.363776 · doi:10.1145/363744.363776
- 10.1145/362851.362880 · doi:10.1145/362851.362880
- 10.1145/362851.362882 · doi:10.1145/362851.362882
Cited by
Items 101–121 of 121
Cooperative peer groups in NICE
Lee, S., Sherwood, R., & Bhattacharjee, B. (2003) · IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428) · doi:10.1109/infcom.2003.1208963 · Cited by 257
Applying intrusion detection systems to wireless sensor networks
Roman, R., Zhou, J., & Lopez, J. (2006) · CCNC 2006. 2006 3rd IEEE Consumer Communications and Networking Conference, 2006. · doi:10.1109/ccnc.2006.1593102 · Cited by 231
“However, the size of the list can be reduced using Bloom filters [16], storing the neighbors’ list of every neighbor as a bit array.”
MethodA Review of bioinformatics tools for bio-prospecting from metagenomic sequence data
Roumpeka, D. D., Wallace, R. J., Escalettes, F., Fotheringham, I., & Watson, M. (2017) · Frontiers in Genetics · doi:10.3389/fgene.2017.00023 · Cited by 199
“Bloom filters are probabilistic data structures which test the membership of an element in a dataset, allowing false positives but no false negatives (Bloom, 1970).”
BackgroundPrivacy-Preserving Patient Similarity Learning in a Federated Environment: Development and Analysis
Lee, J., Sun, J., Wang, F., Wang, S., Jun, C.-H., & Jiang, X. (2018) · JMIR Medical Informatics · doi:10.2196/medinform.7744 · Cited by 196
“Hashing technologies can be applied in many applications such as Bloom filter [32] and cryptography [33].”
InCoder: A Generative Model for Code Infilling and Synthesis
Fried, D., Aghajanyan, A., Lin, J., Wang, S., Wallace, E., Shi, F., Zhong, R., Yih, W.-T., Zettlemoyer, L., & Lewis, M. (2022) · arXiv · doi:10.48550/arxiv.2204.05999 · Cited by 187
“(6)We implement match checking using a Bloom filter [15] whose keys are: the file extension, number of tokens in the file, and an MD5 hash [53] of the sequence of tokens, which is highly accurate at identifying files with exactly matching token sequences.”
MethodKleyko, D., Rachkovskij, D., Osipov, E., & Rahimi, A. (2023) · ACM Computing Surveys · doi:10.1145/3558000 · Cited by 141
Security, Privacy, and Usability in Continuous Authentication: A Survey
Baig, A. F., & Eskeland, S. (2021) · Sensors · doi:10.3390/s21175967 · Cited by 98
“A bloom filter [143] is a space-efficient probabilistic data structure of support membership queries.”
BackgroundBiology and medicine in the landscape of quantum advantages
Cordier, B. A., Sawaya, N. P. D., Guerreschi, G. G., & McWeeney, S. K. (2022) · Journal of The Royal Society Interface · doi:10.1098/rsif.2022.0541 · Cited by 87
“For instance, a number of state-of-the-art algorithms for error correcting sequencing data [56] leverage Bloom filters [440], a probabilistic data structure related to hash tables.”
BackgroundA Comprehensive Review on Secure Biometric-Based Continuous Authentication and User Profiling
Ayeswarya, S., & Singh, K. J. (2024) · IEEE Access · doi:10.1109/access.2024.3411783 · Cited by 66
“A space-effective stochastic data structure of support membership queries is called a BF [134].”
BackgroundA Novel Error-Tolerant Anonymous Linking Code
Schnell, R., Bachteler, T., & Reiher, J. (2020) · doi:10.2139/ssrn.3549247 · Cited by 61
Faithful Embeddings for Knowledge Base Queries
Sun, H., Arnold, A. O., Bedrax-Weiss, T., Pereira, F., & Cohen, W. W. (2020) · arXiv · doi:10.48550/arxiv.2004.03658 · Cited by 51
Preventing generation of verbatim memorization in language models gives a false sense of privacy
Ippolito, D., Tramer, F., Nasr, M., Zhang, C., Jagielski, M., Lee, K., Choquette Choo, C., & Carlini, N. (2023) · Proceedings of the 16th International Natural Language Generation Conference · doi:10.18653/v1/2023.inlg-main.3 · Cited by 28
“…some false positives (labeling an n -gram as memorized when it is in fact not), we can take advantage of probabilistic data structures such as Bloom filters (Bloom, 1970), which admits no false negatives but trades off time and space with the false positive rate (which can be computed exactly).”
BackgroundSecure Federated Submodel Learning
Niu, C., Wu, F., Tang, S., Hua, L., Jia, R., Lv, C., Wu, Z., & Chen, G. (2019) · arXiv · doi:10.48550/arxiv.1911.02254 · Cited by 28
“3) Bloom Filter: Bloom filter, conceived by Bloom in 1970 [67], is a space-efficient probabilistic data structure to represent a set whose elements come from a huge domain.”
BackgroundA Survey on Naming, Name Resolution and Data Routing in Information Centric Networking (ICN)
BARAKABITZE, A. A., XIAOHENG, T., & TAN, G. (2014) · IJARCCE · doi:10.17148/ijarcce.2014.31055 · Cited by 25
“The information item which is forwarded via FNs, uses the Bloom Filter's Forwarding Identifier (FId) to decide where to send the packet [36].”
MethodA survey of structured P2P systems for RDF data storage and retrieval
Filali, I., Bongiovanni, F., Huet, F., & Baude, F. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-23074-5_2 · Cited by 19
Optimization of the mainzelliste software for fast privacy-preserving record linkage
Rohde, F., Franke, M., Sehili, Z., Lablans, M., & Rahm, E. (2021) · Journal of Translational Medicine · doi:10.1186/s12967-020-02678-1 · Cited by 14
“The use of Bloom filters [25] for PPRL has been proposed by Schnell and colleagues [3] and has become the most popular encoding scheme for PPRL in research as well as in real applications [1, 2, 4, 18].”
MethodHAlign-G: rapid and low-memory multiple-genome aligner for large-scale closely related genomes
Zhang, P., Zhou, T., Wei, Y., Tian, Q., Zhai, Y., Wang, Y., Zou, Q., Tang, F., & Luo, X. (2025) · Genome Biology · doi:10.1186/s13059-025-03881-3 · Cited by 12
“It employs a Bloom Filter [57] to count the shared k-mers between each non-central sequence and the forward and reverse k-mer sets of the central sequence.”
A Survey on Data Selection for Language Models
Albalak, A., Elazar, Y., Xie, S. M., Longpre, S., Lambert, N., Wang, X., Muennighoff, N., Hou, B., Pan, L., Jeong, H., et al. (2024) · arXiv · doi:10.48550/arxiv.2402.16827 · Cited by 12
Multiresolution Priority Queues
Ros-Giralt, J., Commike, A., Cullen, P., Lucovsky, J., Madathil, D., & Lethin, R. (2017) · arXiv · Cited by 3
BF2: A Bloom-Filtered Brute-Force Framework for Multi-Target Password Recovery
Aslan, C., Pünter, W., & Dörr, C. (2026) · IACR Communications in Cryptology · doi:10.62056/a6hee0fgx
(2007)
Metadata
- Authors
- Bloom, B. H.
- Venue
- Communications of the ACM
- Published
- 1970-07
- Volume
- 13
- Issue
- 7
- Pages
- 422-426
- ISSN
- 0001-0782 (ISSN-L)
- 1557-7317
- OpenAlex
- W2123845384
- Cited by
- 7,492
- References
- 0
- FWCI
- 2.69
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.