Spectral bloom filters

By Yossi Matias. ACM SIGMOD Conference, 2003

446 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications

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

How researchers see this paper

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

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

The Bloomier filter: an efficient data structure for static support lookup tables (2004, methodology): “Bloom filters are used in distributed databases to support iceberg queries, differential files access, and to compute joins and semijoins [ 7 , 11, 14, 18, 20, 24].”
An Improved Construction for Counting Bloom Filters (2006, methodology): “The spectral Bloom filter was desigend for multi-sets, but also considers schemes to improve the efficiency of storing counters [7].”
Sketch Algorithms for Estimating Point Queries in NLP (2012, methodology): “The idea of conservative update (also known as Minimal Increase (Cohen and Matias, 2003)) is to only increase counts in the sketch by the minimum amount needed to ensure the estimate remains accurate.”
Invertible bloom lookup tables (2011, background): “Cohen and Matias [12] describe an extended Bloom filter that allows for multiplicity queries on multisets.”
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): “The chemical shielding term m l can have both isotropic and anisotropic parts, whereas the D lm terms are completely anisotropic and hence do not contribute to the familiar spectra of isotropic liquids.”
New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice (2003, background): “Gibbons and Matias [1998] consider synopsis data structures that use small amounts of memory to approximately summarize large databases, but their algorithms have also been used for pro.ling program execution [Burrows et al. 2000].”
Network Applications of Bloom Filters: A Survey (2004, unknown): “Cohen and Matias introduce spectral Bloom ﬁ lters [Cohen and Matias 03], which, like the work of Estan and Varghese of Section 8.1, extend the basic Bloom ﬁ lter construction so that it can handle multi-sets.”
Flipping bits in memory without accessing them: An experimental study of DRAM disturbance errors (2014, methodology): “We also analyzed approximate methods which further reduce the storage requirement: Bloom Filters [11], Morris Counters [50], and variants thereof [18, 21, 66].”
Theory and Practice of Bloom Filters for Distributed Systems (2012, methodology): “Spectral Bloom filters generalize Bloom filters to storing an approximate multiset and support frequency queries [32] .”