Compressed bloom filters

By Michael M. Mitzenmacher. ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2001

614 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/e685af30368397c623f146a42b95a46fee1cbd10

How researchers see this paper

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

Citations in the corpus

Theory and Practice of Bloom Filters for Distributed Systems (2012, background): “This structure is particularly useful when informat ion must be transmitted repeatedly, and the bandwidth is a limit ing factor [7].”
Fast, Lean, and Accurate: Modeling Password Guessability Using Neural Networks (2016, methodology): “We stored the first two million most frequently occurring passwords in our training set in a series of compressed Bloom filters [69].”
Secure Indexes (2003, methodology): “Other techniques for reducing the Bloom filter size include using compressed Bloom filters [17].”
On the Feasibility of Peer-to-Peer Web Indexing and Search (2003, background): “Gap compression has the added advantage over Bloom filters as it incurs no extra round-trip time, and the compression ratio is independent of the size of the final intersection.”
Wireless sensor network key management survey and taxonomy (2010, methodology): “Using the Bloom filter (Mitzenmacher, 2002), the sink can apply k system-wide hash functions to map the elements of S (each with Lþ2 bytes) to an m-bit vector V with V 1⁄4 v0v1; .”
The Case for Learned Index Structures (2017, background): “There have been several attempts to improve the efficiency of Bloom filters [52], but the general observation remains.”
Informed content delivery across adaptive overlay networks (2002, background): “bits transmitted between peers at the cost of using more bits to store the Bloom filter at the end systems and requiring compression and decompression at the peers [26].”
SketchVisor: Robust Network Measurement for Software Packet Processing (2017, methodology): “The fast path is volume-based and tracks byte counts, yet we can also use it to track connectivity-based statistics (e.g., DDoS, superspreader, and cardinality) by converting connectivity-based sketches in the normal path into volume-based sketches, similar to the approach in Counting Bloom Filter [”
The Bloomier filter: an efficient data structure for static support lookup tables (2004, methodology): “When the filter is intended to be passed as a message, compressed Bloom filters [23] may be used in-”
Weightless: Lossy Weight Encoding For Deep Neural Network Compression (2017, methodology): “Prior work by Mitzenmacher (2002) on regular Bloom ﬁlters has shown that they can be optimized for better post-compression size.”
Less hashing, same performance: Building a better Bloom filter (2006, background): “Indeed, for a standard Bloom filter, the distinction between the two concepts as we have defined them is unimportant in practice, since one can easily show that R is very close to Pr(F) with extremely high probability (see, for example, [13]).”
Non-commercial Research and Educational Use including without Limitation Use in Instruction at Your Institution, Sending It to Specific Colleagues That You Know, and Providing a Copy to Your Institution's Administrator. All Other Uses, Reproduction and Distribution, including without Limitation Comm (2005, unknown): “Since we only concern ourselves with nuclear spins 1/2 the quadrupolar term has been omitted.”