Space/time trade-offs in hash coding with allowable errors

By B. Bloom. 1970

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Deduplicating Training Data Makes Language Models Better (2021, methodology): “RealNews was dedupli- 229 cated by inserting a hash of the first 100 characters 230 of each document into a bloom filter (Bloom, 1970) 231 and then excluding any document which resulted in 232 a hash collision.”
InCoder: A Generative Model for Code Infilling and Synthesis (2022, methodology): “(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.”
Data Portraits: Recording Foundation Model Training Data (2023, methodology): “Other data sketches, such as Bloom filters [4] and related structures, have a long history of use as efficient storage for NLP tasks.”
Secure Federated Submodel Learning (2019, background): “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.”
PIR with Compressed Queries and Amortized Query Processing (2018, methodology): “In Pung, clients obtain this mapping in a succinct Bloom filter [13].”
#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning (2016, background): “Theory of Bloom Filters Bloom ﬁlters (Bloom, 1970) are popular for determining whether a data sample s 0 belongs to a dataset D .”
Efficient Private Statistics with Succinct Sketches (2015, background): “Ashok et al. [5] present a privacy-preserving protocol for computing the set-union cardinality among several parties using Bloom ﬁlters [10].”
Ad click prediction: a view from the trenches (2013, methodology): “We use a rolling set of counting Bloom ﬁlters [4, 12] to detect the ﬁrst n times a feature is encountered in training.”
Continual Learning in Practice (2019, positive): “A Bloom ﬁlter [13] is a ﬁxed-size set data structure that is optimised for membership queries.”
The evicted-address filter: A unified mechanism to address both cache pollution and thrashing (2012, methodology): “As described in Section 2.3, the EAF is designed to be implementable using a Bloom filter [6].”
Data Integration for the Relational Web (2009, methodology): “We do not require absolute precision from the hitcount numbers, so we saved memory by representing document sets using Bloom Filters [2].”
Bullet: high bandwidth data dissemination using an overlay mesh (2003, methodology): “For this purpose, we use a Bloom lter [ 4 ], a bit array of size m with k independent associated hash functions.”
Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries (2013, background): “The XSet is realized as a RAM-resident Bloom filter [2], which enables the sizing the false positive rate to the lowest value that the server’s RAM allows.”
Spectral bloom filters (2003, background): “Spectral Bloom Filters Saar Cohen School of Computer Science Tel Aviv University saarco@cs.tau.ac.il ABSTRACT A Bloom Filter is a space-e.cient randomized data structure allowing membership queries over sets with certain allowable errors.”
Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams (2012, methodology): “The main techniques we use to achieve aggregator obliviousness include Bloom filters [2] as well as special encryption schemes [15, 20, 21] that support the controlled decryption of selected statistics.”
The CQL continuous query language: semantic foundations and query execution (2006, background): “Example synopsis types for this purpose are reservoir samples [44] over streams and Bloom filters [15].”