The Bloomier filter: an efficient data structure for static support lookup tables

By Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, Ayellet Tal. ACM-SIAM Symposium on Discrete Algorithms, 2004

462 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/182f32790af12408a5656e59356e4ce6873e2066

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

Cuckoo Filter: Practically Better Than Bloom (2014, unknown): “Although variants like Bloomier filters can generalize Bloom filters to represent functions, these structures are more complex and require more space than cuckoo filters [7].”
Randomized Language Models via Perfect Hash Functions (2008, methodology): “Our randomized language model is based on the Bloomier filter (Chazelle et al., 2004).”
Invertible bloom lookup tables (2011, methodology): “, see [2], [4]), we specifically desire a data structure that supports the listing out of all of its key-value pairs.”
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): “In order to describe the orientational order of the solute, the Saupe order matrix S kl is employed, with S kl defined as averages over reorientational motion of the second-order Legendre polynomials: S kl ¼ 1 2 < 3 cos h Z;k cos h Z;l À d kl > ð2Þ where h Z,k is the angle between the…”
Space-efficient and exact de Bruijn graph representation based on a Bloom filter (2012, unknown): “Even for large sizes, the probabilistic graph assemblies diﬀer by more than 3 Kbp to the reference assembly.”
Less hashing, same performance: Building a better Bloom filter (2006, background): “filters keep function values associated with set elements (thereby offering more than set membership) [ 5 ], Count-Min sketches [6] and multistage filters [12] track counts associated with items, and approximate concurrent state machines track the dynamically changing state of a changing set of item”
Weightless: Lossy Weight Encoding For Deep Neural Network Compression (2017, methodology): “In their paper introducing Bloomier ﬁlters, Chazelle et al. (2004) give a greedy algorithm which takes O ( n log n ) time and produces a ⇥ 10 4”
Theory and Practice of Bloom Filters for Distributed Systems (2012, background): “Bloom filters have been generalized to Bloomierfilters [33] that compactly store function values.”