View source for Bloom filter

{{Short description|Data structure for approximate set membership}}
{{Probabilistic}}

A '''Bloom filter''' is a space-efficient probabilistic [[Data structure|data structure]], conceived by Burton Howard Bloom in 1970, that is used to test whether an [[Element (mathematics)|element]] is a member of a set. [[Type I and type II errors|False positive]] matches are possible, but [[Type I and type II errors|false negatives]] are not – in other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed (though this can be addressed with the counting Bloom filter variant); the more items added, the larger the probability of false positives.

The high level idea is to map elements ''x''∈''X'' to values {{tmath|1=y=h(x)\in Y}} using a hash function ''h'', and then test for membership of {{tmath|x' \in X}} by checking whether {{tmath|1=y'=h(x')\in Y}}, and do that using multiple hash functions ''h''.

Bloom proposed the technique for applications where the amount of source data would require an impractically large amount of memory if "conventional" error-free [[Hash function|hashing]] techniques were applied. He gave the example of a [[Hyphenation algorithm|hyphenation algorithm]] for a dictionary of 500,000 words, out of which 90% follow simple hyphenation rules, but the remaining 10% require expensive disk accesses to retrieve specific hyphenation patterns. With sufficient [[Core memory|core memory]], an error-free hash could be used to eliminate all unnecessary disk accesses; on the other hand, with limited core memory, Bloom's technique uses a smaller hash area but still eliminates most unnecessary accesses. For example, a hash area only 15% of the size needed by an ideal error-free hash still eliminates 85% of the disk accesses.{{sfnp|Bloom|1970}}

More generally, fewer than 10 [[Bit|bit]]s per element are required for a 1% false positive probability, independent of the size or number of elements in the set.{{sfnp|Bonomi|Mitzenmacher|Panigrahy|Singh|2006}}

==Algorithm description==
[[File:Bloom filter.svg|thumb|360px|An example of a Bloom filter, representing the set {{math|{''x'', ''y'', ''z''} }}. The colored arrows show the positions in the bit array that each set element is mapped to. The element {{mvar|w}} is not in the set {{math|{''x'', ''y'', ''z''} }}, because it hashes to one bit-array position containing 0. For this figure, {{math|1=''m''&nbsp;= 18}} and {{math|1=k&nbsp;= 3}}.]]

An ''empty Bloom filter'' is a [[Bit array|bit array]] of {{mvar|m}} bits, all set to 0. There must also be {{mvar|k}} different [[Hash function|hash function]]s defined, each of which [[Map (mathematics)|maps]] or hashes some set element to one of the {{mvar|m}} array positions, generating a uniform random distribution.  Typically, {{mvar|k}} is a small constant which depends on the desired false error rate  {{mvar|ε}}, while {{mvar|m}} is proportional to {{mvar|k}} and the number of elements to be added.

To ''add'' an element, feed it to each of the {{mvar|k}} hash functions to get {{mvar|k}} array positions. Set the bits at all these positions to 1.

To ''query'' for an element (test whether it is in the set), feed it to each of the {{mvar|k}} hash functions to get {{mvar|k}} array positions. If ''any'' of the bits at these positions is 0, the element is definitely not in the set; if it were, then all the bits would have been set to 1 when it was inserted. If all are 1, then either the element is in the set, ''or'' the bits have by chance been set to 1 during the insertion of other elements, resulting in a false positive. In a simple Bloom filter, there is no way to distinguish between the two cases, but more advanced techniques can address this problem.

The requirement of designing {{mvar|k}} different independent hash functions can be prohibitive for large {{mvar|k}}. For a good hash function with a wide output, there should be little if any correlation between different bit-fields of such a hash, so this type of hash can be used to generate multiple "different" hash functions by slicing its output into multiple bit fields.  Alternatively, one can pass {{mvar|k}} different initial values (such as 0, 1, ..., {{mvar|k}}&nbsp;&minus;&nbsp;1) to a hash function that takes an initial value; or add (or append) these values to the key. For larger {{mvar|m}} and/or {{mvar|k}}, independence among the hash functions can be relaxed with negligible increase in false positive rate.<ref>{{harvtxt|Dillinger|Manolios|2004a}}; {{harvtxt|Kirsch|Mitzenmacher|2006}}.</ref> (Specifically, {{harvtxt|Dillinger|Manolios|2004b}} show the effectiveness of deriving the {{mvar|k}} indices using [[Double hashing#Enhanced double hashing|enhanced double hashing]]
and [[Double hashing#triple hashing|triple hashing]], variants of [[Double hashing|double hashing]] that are effectively simple random number generators seeded with the two or three hash values.)

Removing an element from this simple Bloom filter is impossible because there is no way to tell which of the {{mvar|k}} bits it maps to should be cleared.  Although setting any one of those {{mvar|k}} bits to zero suffices to remove the element, it would also remove any other elements that happen to map onto that bit. Since the simple algorithm provides no way to determine whether any other elements have been added that affect the bits for the element to be removed, clearing any of the bits would introduce the possibility of false negatives.

One-time removal of an element from a Bloom filter can be simulated by having a second Bloom filter that contains items that have been removed.  However, false positives in the second filter become false negatives in the composite filter, which may be undesirable.  In this approach re-adding a previously removed item is not possible, as one would have to remove it from the "removed" filter.

It is often the case that all the keys are available but are expensive to enumerate (for example, requiring many disk reads).  When the false positive rate gets too high, the filter can be regenerated; this should be a relatively rare event.

==Space and time advantages==
[[File:Bloom filter speed.svg|thumb|360px|Bloom filter used to speed up answers in a key-value storage system. Values are stored on a disk which has slow access times. Bloom filter decisions are much faster. However some unnecessary disk accesses are made when the filter reports a positive (in order to weed out the false positives). Overall answer speed is better with the Bloom filter than without the Bloom filter. Use of a Bloom filter for this purpose, however, does increase memory usage{{citation needed|reason=a single FS access will require a new page in the page cache to be allocated, multiple filters could typically fit in that space, how does this use more memory? Because you have your regular data structures in memory, as well as your Bloom filter. Leave that out and you have less memory used -- exactly one Bloom filter less.|date=May 2019}}.]]

While risking false positives, Bloom filters have a substantial space advantage over other data structures for representing sets, such as [[Self-balancing binary search tree|self-balancing binary search tree]]s, [[Trie|trie]]s, [[Hash table|hash table]]s, or simple [[Array data structure|arrays]] or linked lists of the entries. Most of these require storing at least the data items themselves, which can require anywhere from a small number of bits, for small integers, to an arbitrary number of bits, such as for strings ({{Not a typo|[[Trie|tries]]}} are an exception since they can share storage between elements with equal prefixes).  However, Bloom filters do not store the data items at all, and a separate solution must be provided for the actual storage. Linked structures incur an additional linear space overhead for pointers. A Bloom filter with a 1% error and an optimal value of {{mvar|k}}, in contrast, requires only about 9.6 bits per element, regardless of the size of the elements. This advantage comes partly from its compactness, inherited from arrays, and partly from its probabilistic nature. The 1% false-positive rate can be reduced by a factor of ten by adding only about 4.8 bits per element.

However, if the number of potential values is small and many of them can be in the set, the Bloom filter is easily surpassed by the deterministic [[Bit array|bit array]], which requires only one bit for each potential element. Hash tables gain a space and time advantage if they begin ignoring collisions and store only whether each bucket contains an entry; in this case, they have effectively become Bloom filters with {{math|1={{var|k}} = 1}}.{{sfnp|Mitzenmacher|Upfal|2005}}

Bloom filters also have the unusual property that the time needed either to add items or to check whether an item is in the set is a fixed constant, {{math|O({{var|k}})}}, completely independent of the number of items already in the set. No other constant-space set data structure has this property, but the average access time of sparse [[Hash table|hash table]]s can make them faster in practice than some Bloom filters.  In a hardware implementation, however, the Bloom filter shines because its {{mvar|k}} lookups are independent and can be parallelized.

To understand its space efficiency, it is instructive to compare the general Bloom filter with its special case when {{math|1={{var|k}} = 1}}.  If {{math|1={{var|k}} = 1}}, then in order to keep the false positive rate sufficiently low, a small fraction of bits should be set, which means the array must be very large and contain long runs of zeros.  The [[Information content|information content]] of the array relative to its size is low.  The generalized Bloom filter ({{mvar|k}} greater than 1) allows many more bits to be set while still maintaining a low false positive rate; if the parameters ({{mvar|k}} and {{mvar|m}}) are chosen well, about half of the bits will be set,<ref>{{harvtxt|Blustein|El-Maazawi|2002}}, pp. 21–22</ref> and these will be apparently random, minimizing redundancy and maximizing information content.

==Probability of false positives==
[[File:Bloom filter fp probability.svg|thumb|360px|The false positive probability <math>p</math> as a function of number of elements <math>n</math> in the filter and the filter size <math>m</math>. An optimal number of hash functions <math>k= (m/n) \ln 2</math> has been assumed.]]

Assume that a [[Hash function|hash function]] selects each array position with equal probability. If ''m'' is the number of bits in the array, the probability that a certain bit is not set to 1 by a certain hash function during the insertion of an element is
:<math>1-\frac{1}{m}.</math>

If ''k'' is the number of hash functions and each has no significant correlation between each other, then the probability that the bit is not set to 1 by any of the hash functions is
:<math>\left(1-\frac{1}{m}\right)^k.</math>

We can use the well-known identity for [[E (mathematical constant)|''e'']]<sup>&minus;1</sup>
:<math>\lim_{m\to\infty} \left(1 - \frac{1}{m}\right)^m = \frac{1}{e}</math>
to conclude that, for large ''m'',
:<math>\left(1-\frac{1}{m}\right)^k = \left(\left(1-\frac{1}{m}\right)^m\right)^{k/m} \approx e^{-k/m}.</math>

If we have inserted ''n'' elements, the probability that a certain bit is still 0 is

:<math>\left(1-\frac{1}{m}\right)^{kn} \approx e^{-kn/m};</math>

the probability that it is 1 is therefore

:<math>1-\left(1-\frac{1}{m}\right)^{kn} \approx 1 - e^{-kn/m}.</math>

Now test membership of an element that is not in the set. Each of the ''k'' array positions computed by the hash functions is 1 with a probability as above. The probability of all of them being 1, which would cause the [[Algorithm|algorithm]] to erroneously claim that the element is in the set, is often given as

:<math>\varepsilon = \left(1-\left[1-\frac{1}{m}\right]^{kn}\right)^k \approx \left( 1-e^{-kn/m} \right)^k.</math>

This is not strictly correct as it assumes independence for the probabilities of each bit being set. However, assuming it is a close approximation we have that the probability of false positives decreases as ''m'' (the number of bits in the array) increases, and increases as ''n'' (the number of inserted elements) increases.

The true probability of a false positive, without assuming independence, is

: <math>\frac{1}{m^{k(n+1)}}\sum_{i=1}^m i^k i! {m \choose i} \left\{ {kn \atop i}\right\}</math>

where the {braces} denote [[Stirling numbers of the second kind]].<ref>{{Cite book|last1=Gopinathan|first1=Kiran|last2=Sergey|first2=Ilya|title=Computer Aided Verification |chapter=Certifying Certainty and Uncertainty in Approximate Membership Query Structures |date=2020-07-21|chapter-url= |series=Lecture Notes in Computer Science|volume=12225|language=en|publisher=Springer, Cham|pages=279–303|doi=10.1007/978-3-030-53291-8_16|pmc=7363400|isbn=978-3-030-53290-1}}</ref>

An alternative analysis arriving at the same approximation without the assumption of independence is given by Mitzenmacher and Upfal.<ref>{{harvtxt|Mitzenmacher|Upfal|2005}}, pp. 109–111, 308.</ref> After all ''n'' items have been added to the Bloom filter, let ''q'' be the fraction of the ''m'' bits that are set to 0. (That is, the number of bits still set to 0 is ''qm''.) Then, when testing membership of an element not in the set, for the array position given by any of the ''k'' hash functions, the probability that the bit is found set to 1 is <math>1-q</math>. So the probability that all ''k'' hash functions find their bit set to 1 is <math>(1 - q)^k</math>. Further, the expected value of ''q'' is the probability that a given array position is left untouched by each of the ''k'' hash functions for each of the ''n'' items, which is (as above)
: <math>E[q] = \left(1 - \frac{1}{m}\right)^{kn}</math>.
It is possible to prove, without the independence assumption, that ''q'' is very strongly concentrated around its expected value. In particular, from the Azuma–Hoeffding inequality, they prove that<ref>{{harvtxt|Mitzenmacher|Upfal|2005}}, p. 308.</ref>
: <math> \Pr(\left|q - E[q]\right| \ge \frac{\lambda}{m}) \le 2\exp(-2\lambda^2/kn) </math>
Because of this, we can say that the exact probability of false positives is
: <math> \sum_{t} \Pr(q = t) (1 - t)^k \approx (1 - E[q])^k = \left(1-\left[1-\frac{1}{m}\right]^{kn}\right)^k \approx \left( 1-e^{-kn/m} \right)^k</math>
as before.

===Optimal number of hash functions===
The number of hash functions, ''k'', must be a positive integer.  Putting this constraint aside, for a given ''m'' and ''n'', the value of ''k'' that minimizes the false positive probability is

:<math>k = \frac{m}{n} \ln 2.</math>

The required number of bits, ''m'', given ''n'' (the number of inserted elements) and a desired false positive probability ''ε'' (and assuming the optimal value of ''k'' is used) can be computed by substituting the optimal value of ''k'' in the probability expression above:
:<math>\varepsilon = \left( 1-e^{-(\frac m n \ln 2) \frac n m} \right)^{\frac m n\ln 2}=\left(\frac 1 2 \right)^{\frac m n\ln 2}</math>
which can be simplified to:
:<math>\ln (\varepsilon) = -\frac{m}{n}\ln(2)^2.</math>
This results in:
:<math>m=-\frac{n\ln(\varepsilon)}{\ln (2)^2}</math>
So the optimal number of bits per element is
:<math>\frac{m}{n}=-\frac{\ln(\varepsilon)}{\ln (2)^2}\approx-2.08\ln(\varepsilon)</math>
with the corresponding number of hash functions ''k'' (ignoring integrality):
:<math>k=-\frac{\ln (\varepsilon)}{\ln(2)}. </math>

This means that for a given false positive probability ''ε'', the length of a Bloom filter ''m'' is proportionate to the number of elements being filtered ''n'' and the required number of hash functions only depends on the target false positive probability ''ε''.<ref>{{harvtxt|Starobinski|Trachtenberg|Agarwal|2003}}</ref>

The formula <math>m=-\frac{n\ln\varepsilon}{(\ln 2)^2}</math> is approximate for three reasons.  First, and of least concern, it approximates
<math>1 - \frac{1}{m}</math> as <math>e^{-\frac{1}{m}}</math>, which is a good asymptotic approximation (i.e., which holds as ''m'' →∞).  Second, of more concern, it assumes that during the membership test the event that one tested bit is set to 1 is independent of the event that any other tested bit is set to 1.  Third, of most concern, it assumes that <math>k = \frac{m}{n} \ln 2</math> is fortuitously integral.

Goel and Gupta,<ref>{{harvtxt|Goel|Gupta|2010}}</ref> however, give a rigorous upper bound that makes no approximations and requires no assumptions.  They show that the false positive probability for a finite Bloom filter with ''m'' bits (<math> m > 1</math>), ''n'' elements, and ''k'' hash functions is at most

:<math>\varepsilon \leq \left( 1-e^{-\frac{k(n+0.5)}{m-1}} \right)^k.</math>

This bound can be interpreted as saying that the approximate formula <math>\left( 1-e^{-\frac{kn}m} \right)^k</math> can be applied at a penalty of at most half an extra element and at most one fewer bit.

==Approximating the number of items in a Bloom filter==

{{harvtxt|Swamidass|Baldi|2007}} showed that the number of items in a Bloom filter can be approximated with the following formula,

:<math> n^* = -\frac{m}{k} \ln \left[ 1 - \frac{X}{m} \right], </math>

where <var><math>n^*</math></var> is an estimate of the number of items in the filter, <var>m</var> is the length (size) of the filter, <var>k</var> is the number of hash functions, and <var>X</var> is the number of bits set to one.

===The union and intersection of sets===

Bloom filters are a way of compactly representing a set of items. It is common to try to compute the size of the intersection or union between two sets. Bloom filters can be used to approximate the size of the intersection and union of two sets. {{harvtxt|Swamidass|Baldi|2007}} showed that for two Bloom filters of length {{mvar|m}}, their counts, respectively can be estimated as

:<math> n(A^*) = -\frac{m}{k} \ln \left[ 1 - \frac{|A|} m \right] </math>

and

:<math> n(B^*) = -\frac{m}{k} \ln \left[ 1 - \frac{|B|} m \right]. </math>

The size of their union can be estimated as

:<math> n(A^*\cup B^*) = -\frac{m}{k} \ln \left[ 1 - \frac{|A \cup B|} m \right], </math>

where <math>n(A \cup B)</math> is the number of bits set to one in either of the two Bloom filters.  Finally, the intersection can be estimated as

:<math> n(A^*\cap B^*) = n(A^*) + n(B^*) - n(A^* \cup B^*),</math>

using the three formulas together.

==Interesting properties==
* Unlike a standard [[Hash table|hash table]] using [[Hash table#Open addressing|open addressing]] for collision resolution, a Bloom filter of a fixed size can represent a set with an arbitrarily large number of elements; adding an element never fails due to the data structure "filling up". However, the false positive rate increases steadily as elements are added until all bits in the filter are set to 1, at which point ''all'' queries yield a positive result. With open addressing hashing, false positives are never produced, but performance steadily deteriorates until it approaches linear search.
* [[Union (set theory)|Union]] and [[Intersection (set theory)|intersection]] of Bloom filters with the same size and set of hash functions can be implemented with [[Bitwise operation|bitwise]] OR and AND operations, respectively. The union operation on Bloom filters is lossless in the sense that the resulting Bloom filter is the same as the Bloom filter created from scratch using the union of the two sets. The intersect operation satisfies a weaker property: the false positive probability in the resulting Bloom filter is at most the false-positive probability in one of the constituent Bloom filters, but may be larger than the false positive probability in the Bloom filter created from scratch using the intersection of the two sets.
* Some kinds of [[Engineering:Superimposed code|superimposed code]] can be seen as a Bloom filter implemented with physical [[Biology:Edge-notched card|edge-notched card]]s. An example is Zatocoding, invented by [[Biography:Calvin Mooers|Calvin Mooers]] in 1947, in which the set of categories associated with a piece of information is represented by notches on a card, with a random pattern of four notches for each category.

==Examples==
*[[Biology:Drosophila melanogaster|Fruit flies]] use a modified version of Bloom filters to detect novelty of odors, with additional features including similarity of novel odor to that of previously experienced examples, and time elapsed since previous experience of the same odor.<ref>{{Cite journal|last1=Dasgupta|first1=Sanjoy|last2=Sheehan|first2=Timothy C.|last3=Stevens|first3=Charles F.|last4=Navlakha|first4=Saket|date=2018-12-18|title=A neural data structure for novelty detection|journal=Proceedings of the National Academy of Sciences|language=en|volume=115|issue=51|pages=13093–13098|doi=10.1073/pnas.1814448115|issn=0027-8424|pmc=6304992|pmid=30509984|bibcode=2018PNAS..11513093D |doi-access=free}}</ref>
*The servers of [[Company:Akamai Technologies|Akamai Technologies]], a content delivery provider, use Bloom filters to prevent "one-hit-wonders" from being stored in its disk caches. One-hit-wonders are web objects requested by users just once, something that Akamai found applied to nearly three-quarters of their caching infrastructure. Using a Bloom filter to detect the second request for a web object and caching that object only on its second request prevents one-hit wonders from entering the disk cache, significantly reducing disk workload and increasing disk cache hit rates.{{sfnp|Maggs|Sitaraman|2015}}
* Google [[Software:Bigtable|Bigtable]], [[Software:Apache HBase|Apache HBase]] and [[Software:Apache Cassandra|Apache Cassandra]] and [[Software:PostgreSQL|PostgreSQL]]<ref>{{cite web |title=Bloom index contrib module |url=https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=9ee014fc899a28a198492b074e32b60ed8915ea9 |archive-url=https://web.archive.org/web/20180909043421/https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=9ee014fc899a28a198492b074e32b60ed8915ea9 |url-status=dead |archive-date=2018-09-09 |publisher=Postgresql.org |date=2016-04-01 |access-date=2016-06-18 }}</ref> use Bloom filters to reduce the disk lookups for non-existent rows or columns. Avoiding costly disk lookups considerably increases the performance of a database query operation.<ref>{{harvtxt|Chang|Dean|Ghemawat|Hsieh|2006}}; {{harvtxt|Apache Software Foundation|2012}}.</ref>
* The [[Software:Google Chrome|Google Chrome]] web browser previously used a Bloom filter to identify malicious URLs. Any URL was first checked against a local Bloom filter, and only if the Bloom filter returned a positive result was a full check of the URL performed (and the user warned, if that too returned a positive result).<ref>{{cite web |last=Yakunin |first=Alex |url=http://blog.alexyakunin.com/2010/03/nice-bloom-filter-application.html |title=Alex Yakunin's blog: Nice Bloom filter application |publisher=Blog.alexyakunin.com |date=2010-03-25 |access-date=2014-05-31 |archive-url=https://web.archive.org/web/20101027012345/http://blog.alexyakunin.com/2010/03/nice-bloom-filter-application.html |archive-date=2010-10-27 |url-status=dead }}</ref><ref>{{cite web|url=https://chromiumcodereview.appspot.com/10896048/ |title=Issue 10896048: Transition safe browsing from bloom filter to prefix set. - Code Review |publisher=Chromiumcodereview.appspot.com |access-date=2014-07-03}}</ref>
* Microsoft [[Software:Bing (search engine)|Bing (search engine)]] uses multi-level hierarchical Bloom filters for its search index, [[Software:BitFunnel|BitFunnel]]. Bloom filters provided lower cost than the previous Bing index, which was based on inverted files.<ref>{{cite journal |last1=Goodwin |first1=Bob |last2=Hopcroft |first2=Michael |last3=Luu |first3=Dan |last4=Clemmer |first4=Alex |last5=Curmei |first5=Mihaela |last6=Elnikety |first6=Sameh |last7=Yuxiong |first7=He |title=BitFunnel: Revisiting Signatures for Search |journal=SIGIR |date=2017 |pages=605–614 |doi=10.1145/3077136.3080789 |s2cid=20123252 |url=https://danluu.com/bitfunnel-sigir.pdf|doi-access=free }}</ref>
* The [[Software:Squid|Squid]] [[World Wide Web|Web]] Proxy [[Web cache|Cache]] uses Bloom filters for cache digests.{{sfnp|Wessels|2004}}
* [[Software:Bitcoin|Bitcoin]] used Bloom filters to speed up wallet synchronization until privacy vulnerabilities with the implementation of Bloom filters were discovered.<ref>{{cite web|title=Bloom Filter {{!}} River Glossary|url=https://river.com/learn/terms/b/bloom-filter/|access-date=2020-11-14|website=River Financial|language=en-us}}</ref>
* The Venti archival storage system uses Bloom filters to detect previously stored data.<ref>{{cite web |url=http://plan9.bell-labs.com/magic/man2html/8/venti |title=Plan 9 /sys/man/8/venti |publisher=Plan9.bell-labs.com |access-date=2014-05-31 |url-status=dead |archive-url=https://web.archive.org/web/20140828071451/http://plan9.bell-labs.com/magic/man2html/8/venti |archive-date=2014-08-28 }}</ref>
* The SPIN model checker uses Bloom filters to track the reachable state space for large verification problems.<ref>{{cite web | url=http://spinroot.com/ | title=Spin - Formal Verification}}</ref>
* The [[Software:Cascading|Cascading]] analytics framework uses Bloom filters to speed up asymmetric joins, where one of the joined data sets is significantly larger than the other (often called Bloom join in the database literature).{{sfnp|Mullin|1990}}
* The [[Software:Exim|Exim]] mail transfer agent (MTA) uses Bloom filters in its rate-limit feature.{{citation needed|date=August 2023}}
* Medium uses Bloom filters to avoid recommending articles a user has previously read.<ref>{{cite web|url=https://medium.com/the-story/what-are-bloom-filters-1ec2a50c68ff#.xlkqtn1vy|title=What are Bloom filters?|publisher=Medium |access-date=2015-11-01|date=2015-07-15}}</ref>{{user-generated inline|date=August 2023}}
* [[Finance:Ethereum|Ethereum]] uses Bloom filters for quickly finding logs on the Ethereum blockchain.
* [[Software:Grafana|Grafana]] Tempo uses Bloom filters to improve query performance by storing bloom filters for each backend block. These are accessed on each query to determine the blocks containing data that meets the supplied search criteria<ref>{{cite web|url=https://grafana.com/docs/tempo/latest/operations/caching/|title= Grafana Tempo Documentation - Caching|publisher=Grafana|access-date=2022-11-16}}</ref>

==Alternatives==

Classic Bloom filters use <math>1.44\log_2(1/\varepsilon)</math> bits of space per inserted key, where <math>\varepsilon</math> is the false positive rate of the Bloom filter. However, the space that is strictly necessary for any data structure playing the same role as a Bloom filter is only <math>\log_2(1/\varepsilon)</math> per key.<ref name=":1">{{Cite book |last1=Carter |first1=Larry |last2=Floyd |first2=Robert |last3=Gill |first3=John |last4=Markowsky |first4=George |last5=Wegman |first5=Mark |title=Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 |chapter=Exact and approximate membership testers |date=1978 |pages=59–65 |chapter-url=http://dx.doi.org/10.1145/800133.804332 |location=New York, New York, USA |publisher=ACM Press |doi=10.1145/800133.804332|s2cid=6465743 }}</ref> Hence Bloom filters use 44% more space than an equivalent optimal data structure.

Pagh et al. provide a data structure that uses <math display="inline">(1 + o(1)) n \log_2 (1/\epsilon) + O(n) </math> bits while supporting constant amortized expected-time operations.{{sfnp|Pagh|Pagh|Rao|2005}} Their data structure is primarily theoretical, but it is closely related to the widely-used [[Quotient filter|quotient filter]], which can be parameterized to use<math>(1 + \delta) n \log \epsilon^{-1} + 3n</math> bits of space, for an arbitrary parameter <math>\delta > 0</math>, while supporting <math>O(\delta^{-2})</math>-time operations.<ref>{{Cite journal |last1=Bender |first1=Michael A. |last2=Farach-Colton |first2=Martin |last3=Johnson |first3=Rob |last4=Kraner |first4=Russell |last5=Kuszmaul |first5=Bradley C. |last6=Medjedovic |first6=Dzejla |last7=Montes |first7=Pablo |last8=Shetty |first8=Pradeep |last9=Spillane |first9=Richard P. |last10=Zadok |first10=Erez |date=July 2012 |title=Don't thrash |url=http://dx.doi.org/10.14778/2350229.2350275 |journal=Proceedings of the VLDB Endowment |volume=5 |issue=11 |pages=1627–1637 |doi=10.14778/2350229.2350275 |s2cid=47180056 |issn=2150-8097}}</ref> Advantages of the quotient filter, when compared to the Bloom filter, include its [[Locality of reference|locality of reference]] and the ability to support deletions.

Another alternative to classic Bloom filter is the [[Cuckoo filter|cuckoo filter]], based on space-efficient variants of [[Cuckoo hashing|cuckoo hashing]]. In this case, a hash table is constructed, holding neither keys nor values, but short fingerprints (small hashes) of the keys.  If looking up the key finds a matching fingerprint, then key is probably in the set.  Cuckoo filters support deletions and have better [[Locality of reference|locality of reference]] than Bloom filters.<ref name=":0">{{Cite journal |last1=Even |first1=Tomer |last2=Even |first2=Guy |last3=Morrison |first3=Adam |date=March 2022 |title=Prefix filter |url=http://dx.doi.org/10.14778/3523210.3523211 |journal=Proceedings of the VLDB Endowment |volume=15 |issue=7 |pages=1311–1323 |doi=10.14778/3523210.3523211 |issn=2150-8097}}</ref> Additionally, in some parameter regimes, cuckoo filters can be parameterized to offer nearly optimal space guarantees.<ref name=":0" />

Many alternatives to Bloom filters, including [[Quotient filter|quotient filter]]s and [[Cuckoo filter|cuckoo filter]]s, are based on the idea of hashing keys to random <math>(\log n + \log \epsilon^{-1})
</math>-bit fingerprints, and then storing those fingerprints in a compact hash table. This technique, which was first introduced by Carter et al. in 1978,<ref name=":1" /> relies on the fact that compact hash tables can be implemented to use roughly <math>n \log n</math> bits less space than their non-compact counterparts. Using succinct hash tables, the space usage can be reduced to as little as <math>n \log_2 (e/\epsilon) + o(n) </math> bits<ref>{{Cite book |last1=Bender |first1=Michael A. |last2=Farach-Colton |first2=Martín |last3=Kuszmaul |first3=John |last4=Kuszmaul |first4=William |last5=Liu |first5=Mingmou |chapter=On the optimal time/Space tradeoff for hash tables |date=2022-06-09 |title=Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing |chapter-url=http://dx.doi.org/10.1145/3519935.3519969 |pages=1284–1297 |location=New York, NY, USA |publisher=ACM |doi=10.1145/3519935.3519969|hdl=1721.1/146419 |isbn=9781450392648 |s2cid=240354692 |hdl-access=free }}</ref> while supporting constant-time operations in a wide variety of parameter regimes.

{{harvtxt|Putze|Sanders|Singler|2007}} have studied some variants of Bloom filters that are either faster or use less space than classic Bloom filters. The basic idea of the fast variant is to locate the k hash values associated with each key into one or two blocks having the same size as processor's memory cache blocks (usually 64 bytes). This will presumably improve performance by reducing the number of potential memory cache misses. The proposed variants have however the drawback of using about 32% more space than classic Bloom filters.

The space efficient variant relies on using a single hash function that generates for each key a value in the range <math>\left[0,n/\varepsilon\right]</math> where <math>\varepsilon</math> is the requested false positive rate. The sequence of values is then sorted and compressed using [[Golomb coding]] (or some other compression technique) to occupy a space close to <math>n\log_2(1/\varepsilon)</math> bits. To query the Bloom filter for a given key, it will suffice to check if its corresponding value is stored in the Bloom filter. Decompressing the whole Bloom filter for each query would make this variant totally unusable. To overcome this problem the sequence of  values is divided into small blocks of equal size that are compressed separately. At query time only half a block will need to be decompressed on average. Because of decompression overhead, this variant may be slower than classic Bloom filters but this may be compensated by the fact that a single hash function needs to be computed.

{{harvtxt|Graf|Lemire|2020}} describes an approach called an xor filter, where they store fingerprints in a particular type of perfect hash table, producing a filter which is more memory efficient (<math>1.23\log_2(1/\varepsilon)</math> bits per key) and faster than Bloom or cuckoo filters.  (The time saving comes from the fact that a lookup requires exactly three memory accesses, which can all execute in parallel.)  However, filter creation is more complex than Bloom and cuckoo filters, and it is not possible to modify the set after creation.

==Extensions and applications==

There are over 60 variants of Bloom filters, many surveys of the field, and a continuing churn of applications (see e.g., Luo, ''et al'' <ref name="autogenerated1">{{cite arXiv |last1=Luo |first1=Lailong |last2=Guo |first2=Deke |last3=Ma |first3=Richard T.B. |last4=Rottenstreich |first4=Ori |last5=Luo |first5=Xueshan |title=Optimizing Bloom filter: Challenges, solutions, and comparisons |date=13 Apr 2018 |eprint=1804.04777 |class=cs.DS }}</ref>). Some of the variants differ sufficiently from the original proposal to be breaches from or forks of the original data structure and its philosophy.<ref name="autogenerated1"/> A treatment which unifies Bloom filters with other work on random projections, compressive sensing, and locality sensitive hashing remains to be done (though see Dasgupta, ''et al''<ref>{{cite journal|last1=Dasgupta|first1=Sanjoy|last2=Sheehan|first2=Timothy C.|last3=Stevens|first3=Charles F.|last4=Navlakhae|first4=Saket|date=2018|title=A neural data structure for novelty detection|journal=Proceedings of the National Academy of Sciences|volume=115|issue=51|pages=13093–13098|doi=10.1073/pnas.1814448115|pmc=6304992|pmid=30509984|bibcode=2018PNAS..11513093D |doi-access=free}}</ref> for one attempt inspired by neuroscience).

===Cache filtering===
[[File:BloomFilterDisk.png|thumb|Using a Bloom filter to prevent one-hit-wonders from being stored in a web cache decreased the rate of disk writes by nearly one half, reducing the load on the disks and potentially increasing disk performance.{{sfnp|Maggs|Sitaraman|2015}}|360x360px]]
[[Content delivery network]]s deploy [[Web cache|web cache]]s around the world to cache and serve web content to users with greater performance and reliability. A key application of Bloom filters is their use in efficiently determining which web objects to store in these web caches.  Nearly three-quarters of the URLs accessed from a typical web cache are "one-hit-wonders" that are accessed by users only once and never again. It is clearly wasteful of disk resources to store one-hit-wonders in a web cache, since they will never be accessed again. To prevent caching one-hit-wonders, a Bloom filter is used to keep track of all URLs that are accessed by users.  A web object is cached only when it has been accessed at least once before, i.e., the object is cached on its second request. The use of a Bloom filter in this fashion significantly reduces the disk write workload, since most one-hit-wonders are not written to the disk cache. Further, filtering out the one-hit-wonders also saves cache space on disk, increasing the cache hit rates.{{sfnp|Maggs|Sitaraman|2015}}

===Avoiding false positives in a finite universe===
Kiss ''et al'' <ref>{{cite journal |last1=Kiss |first1=S. Z. |last2=Hosszu |first2=E. |last3=Tapolcai |first3=J. |last4=Rónyai |first4=L. |last5=Rottenstreich |first5=O. |title=Bloom filter with a false positive free zone |journal=IEEE Proceedings of INFOCOM |date=2018 |url=http://lendulet.tmit.bme.hu/lendulet_website/wp-content/papercite-data/pdf/kiss2018bloom.pdf |access-date=4 December 2018}}</ref> described a new construction for the Bloom filter that avoids false positives in addition to the typical non-existence of false negatives. The construction applies to a finite universe from which set elements are taken. It relies on existing non-adaptive combinatorial group testing scheme by Eppstein, Goodrich and Hirschberg. Unlike the typical Bloom filter, elements are hashed to a bit array through deterministic, fast and simple-to-calculate functions. The maximal set size for which false positives are completely avoided is a function of the universe size and is controlled by the amount of allocated memory.

Alternatively, an initial Bloom filter can be constructed in the standard way and then, with a finite and tractably-enumerable domain, all false positives can be exhaustively found and then a second Bloom filter constructed from that list; false positives in the second filter are similarly handled by constructing a third, and so on. As the universe is finite and the set of false positives strictly shrinks with each step, this procedure results in a finite ''cascade'' of Bloom filters that (on this closed, finite domain) will produce only true positives and true negatives. To check for membership in the filter cascade, the initial filter is queried, and, if the result is positive, the second filter is then consulted, and so on. This construction is used in CRLite, a proposed certificate revocation status distribution mechanism for the Web PKI, and [[Certificate Transparency]] is exploited to close the set of extant certificates.<ref>{{ Cite book | doi = 10.1109/sp.2017.17 | doi-access = free | chapter = CRLite: A Scalable System for Pushing All TLS Revocations to All Browsers | title = 2017 IEEE Symposium on Security and Privacy (SP) | year = 2017 | last1 = Larisch | first1 = James | last2 = Choffnes | first2 = David | last3 = Levin | first3 = Dave | last4 = Maggs | first4 = Bruce M. | last5 = Mislove | first5 = Alan | last6 = Wilson | first6 = Christo | pages = 539–556 | isbn = 978-1-5090-5533-3 | s2cid = 3926509 }}</ref>

===Counting Bloom filters===
{{main|Counting Bloom filter}}
Counting filters provide a way to implement a ''delete'' operation on a Bloom filter without recreating the filter afresh. In a counting filter, the array positions (buckets) are extended from being a single bit to being a multibit counter. In fact, regular Bloom filters can be considered as counting filters with a bucket size of one bit. Counting filters were introduced by {{harvtxt|Fan|Cao|Almeida|Broder|2000}}.

The insert operation is extended to ''increment'' the value of the buckets, and the lookup operation checks that each of the required buckets is non-zero. The delete operation then consists of decrementing the value of each of the respective buckets.

[[Arithmetic overflow]] of the buckets is a problem and the buckets should be sufficiently large to make this case rare. If it does occur then the increment and decrement operations must leave the bucket set to the maximum possible value in order to retain the properties of a Bloom filter.

The size of counters is usually 3 or 4 bits. Hence counting Bloom filters use 3 to 4 times more space than static Bloom filters. In contrast, the data structures of {{harvtxt|Pagh|Pagh|Rao|2005}} and {{harvtxt|Fan|Andersen|Kaminsky|Mitzenmacher|2014}} also allow deletions but use less space than a static Bloom filter.

Another issue with counting filters is limited scalability. Because the counting Bloom filter table cannot be expanded, the maximal number of keys to be stored simultaneously in the filter must be known in advance. Once the designed capacity of the table is exceeded, the false positive rate will grow rapidly as more keys are inserted.

{{harvtxt|Bonomi|Mitzenmacher|Panigrahy|Singh|2006}} introduced a data structure based on d-left hashing that is functionally equivalent  but uses approximately half as much space as counting Bloom filters. The scalability issue does not occur in this data structure. Once the designed capacity is exceeded, the keys could be reinserted in a new hash table of double size.

The space efficient variant by {{harvtxt|Putze|Sanders|Singler|2007}} could also be used to implement counting filters by supporting insertions and deletions.

{{harvtxt|Rottenstreich|Kanizo|Keslassy|2012}} introduced a new general method based on variable increments that significantly improves the false positive probability of counting Bloom filters and their variants, while still supporting deletions. Unlike counting Bloom filters, at each element insertion, the hashed counters are incremented by a hashed variable increment instead of a unit increment. To query an element, the exact values of the counters are considered and not just their positiveness. If a sum represented by a counter value cannot be composed of the corresponding variable increment for the queried element, a negative answer can be returned to the query.

[https://www.mdpi.com/2079-9292/8/7/779 Kim et al. (2019)] shows that false positive of Counting Bloom filter decreases from k=1 to a point defined <math>k_{opt}</math>, and increases from <math>k_{opt}</math>to positive infinity, and finds <math>k_{opt}</math>as a function of count threshold.<ref>{{Cite journal|last1=Kim|first1=Kibeom|last2=Jeong|first2=Yongjo|last3=Lee|first3=Youngjoo|last4=Lee|first4=Sunggu|date=2019-07-11|title=Analysis of Counting Bloom Filters Used for Count Thresholding|journal=Electronics|volume=8|issue=7|page=779|doi=10.3390/electronics8070779|issn=2079-9292|doi-access=free}}</ref>

===Decentralized aggregation===
Bloom filters can be organized in distributed data structures to perform fully decentralized computations of [[Aggregate function|aggregate function]]s. Decentralized aggregation makes collective measurements locally available in every node of a distributed network without involving a centralized computational entity for this purpose.{{sfnp|Pournaras|Warnier|Brazier|2013}}

===Distributed Bloom filters===
[[File:DistributedBloomFilterExample.png|400px|thumb|right|Distributed Single Shot Bloom filter for duplicate detection with false positive rate: 6 elements are distributed over 3 PEs, each with a bit array of length 4. During the first communication step PE 1 receives the hash '2' twice and sends it back to either PE 2 or 3, depending on who sent it later. The PE that receives the hash '2' then searches for the element with that hash and marks it as possible duplicate.]]
Parallel Bloom filters can be implemented to take advantage of the multiple processing elements (PEs) present in [[Shared-nothing architecture|parallel shared-nothing machines]]. One of the main obstacles for a parallel Bloom filter is the organization and communication of the unordered data which is, in general, distributed evenly over all PEs at the initiation or at batch insertions. To order the data two approaches can be used, either resulting in a Bloom filter over all data being stored on each PE, called replicating bloom filter, or the Bloom filter over all data being split into equal parts, each PE storing one part of it.<ref>{{cite book |author1=Sanders, Peter |author2=Schlag, Sebastian |author3=Müller, Ingo |title=2013 IEEE International Conference on Big Data |chapter=Communication efficient algorithms for fundamental big data problems |date=2013 |pages=15–23|doi=10.1109/BigData.2013.6691549 |isbn=978-1-4799-1293-3 |s2cid=15968541 }}</ref> For both approaches a "Single Shot" Bloom filter is used which only calculates one hash, resulting in one flipped bit per element, to reduce the communication volume.

'''Distributed Bloom filters''' are initiated by first hashing all elements on their local PE and then sorting them by their hashes locally. This can be done in linear time using e.g. [[Bucket sort]] and also allows local duplicate detection. The sorting is used to group the hashes with their assigned PE as separator to create a Bloom filter for each group. After encoding these Bloom filters using e.g. [[Golomb coding]] each bloom filter is sent as packet to the PE responsible for the hash values that where inserted into it. A PE p is responsible for all hashes between the values <math>p*(s/|\text{PE}|)</math> and <math>(p+1)*(s/|\text{PE}|)</math>, where s is the total size of the Bloom filter over all data. Because each element is only hashed once and therefore only a single bit is set, to check if an element was inserted into the Bloom filter only the PE responsible for the hash value of the element needs to be operated on. Single insertion operations can also be done efficiently because the Bloom filter of only one PE has to be changed, compared to Replicating Bloom filters where every PE would have to update its Bloom filter. 
By distributing the global Bloom filter over all PEs instead of storing it separately on each PE the Bloom filters size can be far larger, resulting in a larger capacity and lower false positive rate. <br />
Distributed Bloom filters can be used to improve duplicate detection algorithms<ref>{{cite journal |last1=Schlag |first1=Sebastian |title=Distributed duplicate removal |journal=Karlsruhe Institute of Technology |date=2013}}</ref> by filtering out the most 'unique' elements. These can be calculated by communicating only the hashes of elements, not the elements themselves which are far larger in volume, and removing them from the set, reducing the workload for the duplicate detection algorithm used afterwards.

During the communication of the hashes the PEs search for bits that are set in more than one of the receiving packets, as this would mean that two elements had the same hash and therefore could be duplicates. If this occurs a message containing the index of the bit, which is also the hash of the element that could be a duplicate, is sent to the PEs which sent a packet with the set bit. If multiple indices are sent to the same PE by one sender it can be advantageous to encode the indices as well. All elements that didn't have their hash sent back are now guaranteed to not be a duplicate and won't be evaluated further, for the remaining elements a Repartitioning algorithm<ref>{{cite journal |author1=Shatdal, Ambuj |author2=Jeffrey F. Naughton |title=Processing aggregates in parallel database systems |journal=University of Wisconsin-Madison Department of Computer Sciences |date=1994 |page=8}}</ref> can be used. First all the elements that had their hash value sent back are sent to the PE that their hash is responsible for. Any element and its duplicate is now guaranteed to be on the same PE. In the second step each PE uses a sequential algorithm for duplicate detection on the receiving elements, which are only a fraction of the amount of starting elements. By allowing a false positive rate for the duplicates, the communication volume can be reduced further as the PEs don't have to send elements with duplicated hashes at all and instead any element with a duplicated hash can simply be marked as a duplicate. As a result, the false positive rate for duplicate detection is the same as the false positive rate of the used bloom filter.

The process of filtering out the most 'unique' elements can also be repeated multiple times by changing the hash function in each filtering step. If only a single filtering step is used it has to archive a small false positive rate, however if the filtering step is repeated once the first step can allow a higher false positive rate while the latter one has a higher one but also works on less elements as many have already been removed by the earlier filtering step. While using more than two repetitions can reduce the communication volume further if the number of duplicates in a set is small, the payoff for the additional complications is low.

'''Replicating Bloom filters''' organize their data by using a well known [[Hypercube|hypercube]] algorithm for gossiping, e.g.<ref>{{cite book |author1=V. Kumar |author2=A. Grama |author3=A. Gupta |author4=G. Karypis |title=Introduction to Parallel Computing. Design and Analysis of Algorithms |date=1994 |publisher=Benjamin/Cummings}}</ref> First each PE calculates the Bloom filter over all local elements and stores it. By repeating a loop where in each step i the PEs send their local Bloom filter over dimension i and merge the Bloom filter they receive over the dimension with their local Bloom filter, it is possible to double the elements each Bloom filter contains in every iteration. After sending and receiving Bloom filters over all <math>\log |\text{PE}|</math> dimensions each PE contains the global Bloom filter over all elements.

Replicating Bloom filters are more efficient when the number of queries is much larger than the number of elements that the Bloom filter contains, the break even point compared to Distributed Bloom filters is approximately after <math>|\text{PE}| * |\text{Elements}| / \log_{f^\text{+}} |\text{PE}|</math> accesses, with <math>f^\text{+}</math> as the false positive rate of the bloom filter.

===Data synchronization===
Bloom filters can be used for approximate [[Data synchronization|data synchronization]] as in {{harvtxt|Byers|Considine|Mitzenmacher|Rost|2004}}.  Counting Bloom filters can be used to approximate the number of differences between two sets and this approach is described in {{harvtxt|Agarwal|Trachtenberg|2006}}.

===Bloom filters for streaming data<span class="anchor" id="Streaming"></span><span class="anchor" id="STABLE"></span>===
Bloom filters can be adapted to the context of streaming data. For instance, {{harvtxt|Deng|Rafiei|2006}} proposed Stable Bloom filters, which consist of a counting Bloom filter where insertion of a new element sets the associated counters to a value {{mvar|c}}, and then only a fixed amount {{mvar|s}} of counters are decreased by 1, hence the memory mostly contains information about recent elements (intuitively, one could assume that the lifetime of an element inside a SBF of {{mvar|N}} counters is around <math>c \tfrac s N</math>). Another solution is the Aging Bloom filter, that consists of two Bloom filter each occupying half the total available memory: when one filter is full, the second filter is erased and newer elements are then added to this newly empty filter.<ref name="AgingBloom">{{cite journal |last1=Yoon |first1=MyungKeun |title=Aging Bloom Filter with Two Active Buffers for Dynamic Sets |journal=IEEE Transactions on Knowledge and Data Engineering |date=2010 |volume=22 |issue=1 |pages=134–138 |doi=10.1109/TKDE.2009.136|s2cid=15922054 }}</ref>

However, it has been shown<ref>{{cite book |last1=Géraud-Stewart |first1=Rémi |last2=Lombard-Platet |first2=Marius |last3=Naccache |first3=David |title=Computing and Combinatorics |chapter=Approaching Optimal Duplicate Detection in a Sliding Window |series=Lecture Notes in Computer Science |date=2020 |volume=12273 |pages=64–84 |doi=10.1007/978-3-030-58150-3_6 |arxiv=2005.04740 |isbn=978-3-030-58149-7 |s2cid=218581915 }}</ref> that no matter the filter, after {{mvar|n}} insertions, the sum of the false positive <math>FP</math> and false negative <math>FN</math> probabilities is bounded below by <math display="block"> FP + FN \geq 1 - \frac{1 - \left(1 - \frac {1}{L} \right)^m}{1 - \left( 1 - \frac {1}{L} \right)^{n}}</math> where {{mvar|L}} is the amount of all possible elements (the alphabet size), {{mvar|m}} the memory size (in bits), assuming <math>n > m</math>. This result shows that for {{mvar|L}} big enough and {{mvar|n}} going to infinity, then the lower bound converges to <math>FP + FN = 1</math>, which is the characteristic relation of a random filter. Hence, after enough insertions, and if the alphabet is too big to be stored in memory (which is assumed in the context of probabilistic filters), it is impossible for a filter to perform better than randomness. This result can be leveraged by only expecting a filter to operate on a sliding window rather than the whole stream. In this case, the exponent {{mvar|n}} in the formula above is replaced by {{mvar|w}}, which gives a formula that might deviate from 1, if {{mvar|w}} is not too small.

===Bloomier filters===
{{harvtxt|Chazelle|Kilian|Rubinfeld|Tal|2004}} designed a generalization of Bloom filters that could associate a value with each element that had been inserted, implementing an [[Associative array|associative array]]. Like Bloom filters, these structures achieve a small space overhead by accepting a small probability of false positives. In the case of "Bloomier filters", a ''false positive'' is defined as returning a result when the key is not in the map. The map will never return the wrong value for a key that ''is'' in the map.
<!-- too wordy for an alternative to the article topic. commented out in case someone wants to move it to a new article.
The simplest Bloomier filter is near-optimal and fairly simple to describe. Suppose initially that the only possible values are 0 and 1. We create a pair of Bloom filters ''A''<sub>0</sub> and ''B''<sub>0</sub> which contain, respectively, all keys mapping to 0 and all keys mapping to 1. Then, to determine which value a given key maps to, we look it up in both filters. If it is in neither, then the key is not in the map. If the key is in ''A''<sub>0</sub> but not ''B''<sub>0</sub>, then it does not map to 1, and has a high probability of mapping to 0. Conversely, if the key is in ''B''<sub>0</sub> but not ''A''<sub>0</sub>, then it does not map to 0 and has a high probability of mapping to 1.

A problem arises, however, when ''both'' filters claim to contain the key. We never insert a key into both, so one or both of the filters is lying (producing a false positive), but we don't know which. To determine this, we have another, smaller pair of filters ''A''<sub>1</sub> and ''B''<sub>1</sub>. ''A''<sub>1</sub> contains keys that map to 0 and which are false positives in ''B''<sub>0</sub>; ''B''<sub>1</sub> contains keys that map to 1 and which are false positives in ''A''<sub>0</sub>. But whenever ''A''<sub>0</sub> and ''B''<sub>0</sub> both produce positives, at most one of these cases must occur, and so we simply have to determine which if any of the two filters ''A''<sub>1</sub> and ''B''<sub>1</sub> contains the key, another instance of our original problem.

It may so happen again that both filters produce a positive; we apply the same idea recursively to solve this problem. Because each pair of filters only contains keys that are in the map ''and'' produced false positives on all previous filter pairs, the number of keys is extremely likely to quickly drop to a very small quantity that can be easily stored in an ordinary deterministic map, such as a pair of small arrays with linear search. Moreover, the average total search time is low, because almost all queries will be resolved by the first pair, almost all remaining queries by the second pair, and so on. The total space required is in practice independent of ''n'', and is almost entirely occupied by the first filter pair.

Now that we have the structure and a search algorithm, we also need to know how to insert new key/value pairs. The program must not attempt to insert the same key with both values. If the value is 0, insert the key into ''A''<sub>0</sub> and then test if the key is in ''B''<sub>0</sub>. If so, this is a false positive for ''B''<sub>0</sub>, and the key must also be inserted into ''A''<sub>1</sub> recursively in the same manner. If we reach the last level, we simply insert it. When the value is 1, the operation is similar but with ''A'' and ''B'' reversed.

Now that we can map a key to the value 0 or 1, how does this help us map to general values? This is simple. We create a single such Bloomier filter for each bit of the result. If the values are large, we can instead map keys to hash values that can be used to retrieve the actual values. The space required for a Bloomier filter with ''n''-bit values is typically slightly more than the space for 2''n'' Bloom filters.

A very simple way to implement Bloomier filters is by means of minimal perfect hashing. A minimal perfect hash function h is first generated for the set of n keys. Then an array is filled with n pairs (signature,value) associated with each key at the positions given by function h when applied on each key. The signature of a key is a string of r bits computed by applying a hash function g of range <math>2^r</math> on the key. The value of r is chosen such that <math>2^r>=1/\varepsilon</math>, where <math>\varepsilon</math> is the requested false positive rate. To query for a given key, hash function h is first applied on the key. This will give a position into the array from which we retrieve a pair (signature,value). Then we compute the signature of the key using function g. If the computed signature is the same as retrieved signature we return the retrieved value. The probability of false positive is <math>1/2^r</math>.

Another alternative to implement static Bloomier and Bloom filters based on matrix solving has been simultaneously proposed in {{harvtxt|Porat|2008}}, {{harvtxt|Dietzfelbinger|Pagh|2008}} and {{harvtxt|Charles|Chellapilla|2008}}. The space usage of this method is optimal as it needs only <math>\log_2(\varepsilon)</math> bits per key for a Bloom filter. However time to generate the Bloom or Bloomier filter can be very high. The generation  time can be reduced to a reasonable value at the price of a small increase in space usage.

Dynamic Bloomier filters have been studied by {{harvtxt|Mortensen|Pagh|Pătrașcu|2005}}. They proved that any dynamic Bloomier filter needs at least around
<math>\log(l)</math> bits per key where l is the length of the key. A simple dynamic version of Bloomier filters can be implemented using two dynamic data structures. Let the two data structures be noted S1 and S2. S1 will store keys with their associated data while S2 will only store signatures of keys with their associated data. Those signatures are simply hash values of keys in the range <math>[0,n/\varepsilon]</math> where n is the maximal number of keys to be stored in the Bloomier filter and <math>\varepsilon</math> is the requested false positive rate. To insert a key in the Bloomier filter, its hash value is first computed. Then the algorithm checks if a key with the same hash value already exists in S2. If this is not the case, the hash value is inserted in S2 along with data associated with the key. If the same hash value already exists in S2 then the key is inserted into S1 along with its associated data. The deletion is symmetric: if the key already exists in S1 it will be deleted from there, otherwise the hash value associated with the key is deleted from S2. An issue with this algorithm is on how to store efficiently S1 and S2. For S1 any hash algorithm can be used. To store S2 [[Golomb coding|golomb coding]] could be applied to compress signatures to use a space close to <math>\log2(1/\varepsilon)</math> per key. -->

===Compact approximators===
{{harvtxt|Boldi|Vigna|2005}} proposed a [[Lattice (order)|lattice]]-based generalization of Bloom filters. A '''compact approximator''' associates to each key an element of a lattice (the standard Bloom filters being the case of the Boolean two-element lattice). Instead of a bit array, they have an array of lattice elements. When adding a new association between a key and an element of the lattice, they compute the maximum of the current contents of the <var>k</var> array locations associated to the key with the lattice element. When reading the value associated to a key, they compute the minimum of the values found in the <var>k</var> locations associated to the key. The resulting value approximates from above the original value.

===Parallel-partitioned Bloom filters===
This implementation used a separate array for each hash function. This method allows for parallel hash calculations for both insertions and inquiries.<ref>{{cite web |last1=Kirsch |first1=Adam |last2=Mitzenmacher† |first2=Michael |title=Less Hashing, Same Performance: Building a Better Bloom Filter |url=https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf |website=Harvard School of Engineering and Applied Sciences |publisher=Wiley InterScience}}</ref>

==={{Anchor|SCALABLE}}Scalable Bloom filters===
{{harvtxt|Almeida|Baquero|Preguica|Hutchison|2007}} proposed a variant of Bloom filters that can adapt dynamically to the number of elements stored, while assuring a minimum false positive probability. The technique is based on sequences of standard Bloom filters with increasing capacity and tighter false positive probabilities, so as to ensure that a maximum false positive probability can be set beforehand, regardless of the number of elements to be inserted.

==={{Anchor|SPATIAL}}Spatial Bloom filters===
Spatial Bloom filters (SBF) were originally proposed by {{harvtxt|Palmieri|Calderoni|Maio|2014}} as a data structure designed to store location information, especially in the context of cryptographic protocols for location [[Information privacy|privacy]]. However, the main characteristic of SBFs is their ability to store '''multiple sets''' in a single data structure, which makes them suitable for a number of different application scenarios.{{sfnp|Calderoni|Palmieri|Maio|2015}} Membership of an element to a specific set can be queried, and the false positive probability depends on the set: the first sets to be entered into the filter during construction have higher false positive probabilities than sets entered at the end.{{sfnp|Calderoni|Palmieri|Maio|2018}} This property allows a prioritization of the sets, where sets containing more "important" elements can be preserved.

==={{Anchor|LAYERED}}Layered Bloom filters===
A layered Bloom filter consists of multiple Bloom filter layers. Layered Bloom filters allow keeping track of how many times an item was added to the Bloom filter by checking how many layers contain the item. With a layered Bloom filter a check operation will normally return the deepest layer number the item was found in.{{sfnp|Zhiwang|Jungang|Jian|2010}}

==={{Anchor|ATTENUATED}}Attenuated Bloom filters===
[[File:AttenuatedBloomFilter2.png|thumb|Attenuated Bloom Filter Example: Search for pattern 11010, starting from node n1.]]

An attenuated Bloom filter of depth D can be viewed as an array of D normal Bloom filters. In the context of service discovery in a network, each node stores regular and attenuated Bloom filters locally. The regular or local Bloom filter indicates which services are offered by the node itself. The attenuated filter of level i indicates which services can be found on nodes that are i-hops away from the current node. The i-th value is constructed by taking a union of local Bloom filters for nodes i-hops away from the node.{{sfnp|Koucheryavy|Giambene|Staehle|Barcelo-Arroyo|2009}}

Let's take a small network shown on the graph below as an example. Say we are searching for a service A whose id hashes to bits 0,1, and 3 (pattern 11010). Let n1 node to be the starting point. First, we check whether service A is offered by n1 by checking its local filter. Since the patterns don't match, we check the attenuated Bloom filter in order to determine which node should be the next hop. We see that n2 doesn't offer service A but lies on the path to nodes that do. Hence, we move to n2 and repeat the same procedure. We quickly find that n3 offers the service, and hence the destination is located.{{sfnp|Kubiatowicz|Bindel|Czerwinski|Geels|2000}}

By using attenuated Bloom filters consisting of multiple layers, services at more than one hop distance can be discovered while avoiding saturation of the Bloom filter by attenuating (shifting out) bits set by sources further away.{{sfnp|Koucheryavy|Giambene|Staehle|Barcelo-Arroyo|2009}}

===Chemical structure searching===
Bloom filters are often used to search large chemical structure databases (see [[Chemistry:Chemical similarity|chemical similarity]]). In the simplest case, the elements added to the filter (called a fingerprint in this field) are just the atomic numbers present in the molecule, or a hash based on the atomic number of each atom and the number and type of its bonds. This case is too simple to be useful. More advanced filters also encode atom counts, larger substructure features like carboxyl groups, and graph properties like the number of rings. In hash-based fingerprints, a hash function based on atom and bond properties is used to turn a subgraph into a [[Pseudorandom number generator|PRNG]] seed, and the first output values used to set bits in the Bloom filter.

Molecular fingerprints started in the late 1940s as way to search for chemical structures searched on punched cards. However, it wasn't until around 1990 that Daylight Chemical Information Systems, Inc. introduced a hash-based method to generate the bits, rather than use a precomputed table. Unlike the dictionary approach, the hash method can assign bits for substructures which hadn't previously been seen. In the early 1990s, the term "fingerprint" was considered different from "structural keys", but the term has since grown to encompass most molecular characteristics which can be used for a similarity comparison, including structural keys, sparse count fingerprints, and 3D fingerprints. Unlike Bloom filters, the Daylight hash method allows the number of bits assigned per feature to be a function of the feature size, but most implementations of Daylight-like fingerprints use a fixed number of bits per feature, which makes them a Bloom filter. The original Daylight fingerprints could be used for both similarity and screening purposes. Many other fingerprint types, like the popular ECFP2, can be used for similarity but not for screening because they include local environmental characteristics that introduce false negatives when used as a screen. Even if these are constructed with the same mechanism, these are not Bloom filters because they cannot be used to filter.

==See also==

* {{Annotated link |Count–min sketch}}
* {{Annotated link |Feature hashing}}
* {{Annotated link |MinHash}}
* {{Annotated link |Quotient filter}}
* {{Annotated link |Skip list}}
* {{Annotated link |Bloom filters in bioinformatics}}
* {{Annotated link |Cuckoo filter}}

==References==

===Citations===
{{Reflist|colwidth=30em}}

===Works cited===
{{Refbegin|colwidth=30em}}
*{{Cite book
 | first1 = Sachin
 | last1 = Agarwal
 | first2 = Ari
 | last2 = Trachtenberg
 | title = 2006 IEEE Information Theory Workshop
 | chapter = Approximating the number of differences between remote sets
 | location = Punta del Este, Uruguay
 | year = 2006
 | doi = 10.1109/ITW.2006.1633815
 | url = http://ipsit.bu.edu/documents/wrap-web.pdf
 | page = 217
 | isbn = 978-1-4244-0035-5
 | citeseerx = 10.1.1.69.1033
 | s2cid = 2048278
 }}
*{{Citation
 | doi = 10.1109/ICON.2007.4444089
 | first1 = Mahmood| last1 = Ahmadi
 | first2 = Stephan| last2 = Wong  | contribution = A Cache Architecture for Counting Bloom Filters
 | title = 15th international Conference on Networks (ICON-2007)
 | year = 2007
 | page = 218 | isbn = 978-1-4244-1229-7| citeseerx = 10.1.1.125.2470| s2cid = 2967865}}
*{{Citation
| first1 = Paulo
| last1 = Almeida
| first2 = Carlos
| last2 = Baquero
| first3 = Nuno
| last3 = Preguica
| first4 = David
| last4 = Hutchison
| title = Scalable Bloom Filters
| journal = Information Processing Letters
| volume = 101
| issue = 6
| year = 2007
| doi = 10.1016/j.ipl.2006.10.007
| url = http://gsd.di.uminho.pt/members/cbm/ps/dbloom.pdf
| pages = 255–261
| hdl = 1822/6627
| hdl-access = free
}}
*{{citation|author=Apache Software Foundation|year=2012|contribution-url=http://hbase.apache.org/0.94/book/perf.schema.html|contribution=11.6. Schema Design|title=The Apache HBase Reference Guide, Revision 0.94.27}}
*{{Citation
 | first = Burton H. | last = Bloom
 | title = Space/Time Trade-offs in Hash Coding with Allowable Errors
 | journal = [[Communications of the ACM]]
 | volume = 13 | issue = 7 | year = 1970 | pages = 422–426
 | doi = 10.1145/362686.362692| citeseerx = 10.1.1.641.9096
 | s2cid = 7931252
 }}
*{{Citation |first1 = James |last1 = Blustein |first2 = Amal |last2 = El-Maazawi |contribution = optimal case for general Bloom filters |title = Bloom Filters — A Tutorial, Analysis, and Survey |year = 2002 |pages = 1–31 |publisher = Dalhousie University Faculty of Computer Science |url = https://www.cs.dal.ca/research/techreports/cs-2002-10 }}
*{{Citation
 | first1 = Paolo | last1 = Boldi
 | first2 = Sebastiano | last2 = Vigna
 | title = Mutable strings in Java: design, implementation and lightweight text-search algorithms
 | journal = Science of Computer Programming
 | volume = 54 | issue = 1 | year = 2005 | pages = 3–23
 | doi = 10.1016/j.scico.2004.05.003| doi-access = }}
*{{Citation
 | first1 = Flavio
 | last1 = Bonomi
 | first2 = Michael
 | last2 = Mitzenmacher
 | first3 = Rina
 | last3 = Panigrahy
 | first4 = Sushil
 | last4 = Singh
 | first5 = George
 | last5 = Varghese
 | contribution = An Improved Construction for Counting Bloom Filters
 | title = Algorithms – ESA 2006, 14th Annual European Symposium
 | year = 2006
 | pages = 684–695
 | doi = 10.1007/11841036_61
 | url = http://theory.stanford.edu/~rinap/papers/esa2006b.pdf
 | volume = 4168
 | series = [[Lecture Notes in Computer Science]]
 | isbn = 978-3-540-38875-3
 }}
*{{Citation | first1 = Andrei | last1 = Broder |  first2 = Michael | last2 = Mitzenmacher |  title = Network Applications of Bloom Filters: A Survey | journal = Internet Mathematics | volume = 1 | issue = 4 | pages = 485–509 | year = 2005 | url = http://www.eecs.harvard.edu/~michaelm/postscripts/im2005b.pdf | doi = 10.1080/15427951.2004.10129096 | s2cid = 1560675 | doi-access = free }}
*{{Citation
 | first1 = John W. | last1 = Byers
 | first2 = Jeffrey | last2 = Considine
 | first4 = Stanislav | last4 = Rost
 | journal = IEEE/ACM Transactions on Networking
 | title = Informed content delivery across adaptive overlay networks
 | volume = 12
 | year = 2004
 | doi = 10.1109/TNET.2004.836103
 | page = 767
 | issue = 5| citeseerx = 10.1.1.207.1563
 | s2cid = 47088273
 }}
*{{citation
 | last1 = Calderoni
 | first1 = Luca
 | last2 = Palmieri
 | first2 = Paolo
 | last3 = Maio
 | first3 = Dario
 | title = Location privacy without mutual trust: The spatial Bloom filter
 | journal = Computer Communications
 | pages = 4–16
 | volume = 68
 | year = 2015
 | doi = 10.1016/j.comcom.2015.06.011
 | issn = 0140-3664
 | hdl = 10468/4762
 | url = http://eprints.bournemouth.ac.uk/22802/4/Palmieri.pdf
 }}
*{{citation
 | last1 = Calderoni | first1 = Luca
 | last2 = Palmieri| first2 = Paolo
 | last3 = Maio | first3 = Dario
 | title = Probabilistic Properties of the Spatial Bloom Filters and Their Relevance to Cryptographic Protocols
 | journal = IEEE Transactions on Information Forensics and Security
 | pages = 1710–1721
 | volume = 13
 | number= 7
 | year = 2018
 | doi = 10.1109/TIFS.2018.2799486
 | issn = 1556-6013
 | hdl = 10468/5767
 | s2cid = 3693354
 | hdl-access = free
 }}
*{{Citation
 | first1 = Fay
 | last1 = Chang
 | first2 = Jeffrey
 | last2 = Dean
 | first3 = Sanjay
 | last3 = Ghemawat
 | first4 = Wilson
 | last4 = Hsieh
 | first5 = Deborah
 | last5 = Wallach
 | first6 = Mike
 | last6 = Burrows
 | first7 = Tushar
 | last7 = Chandra
 | first8 = Andrew
 | last8 = Fikes
 | first9 = Robert
 | last9 = Gruber
 | contribution = Bigtable: A Distributed Storage System for Structured Data
 | title = Seventh Symposium on Operating System Design and Implementation
 | year = 2006
 | url = http://research.google.com/archive/bigtable.html
 }}
*{{citation
 | last1 = Charles | first1 = Denis Xavier
 | last2 = Chellapilla | first2 = Kumar
 | editor1-last = Halperin | editor1-first = Dan
 | editor2-last = Mehlhorn | editor2-first = Kurt
 | arxiv = 0807.0928
 | contribution = Bloomier filters: A second look
 | doi = 10.1007/978-3-540-87744-8_22
 | pages = 259–270
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Algorithms: ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15–17, 2008, Proceedings
 | volume = 5193
 | year = 2008| isbn = 978-3-540-87743-1
 | s2cid = 643445
 }}
*{{Citation | first1 = Bernard | last1 = Chazelle |  first2 = Joe | last2 = Kilian | first3 = Ronitt | last3 = Rubinfeld |  first4 = Ayellet | last4 = Tal | author4-link = Ayellet Tal | contribution = The Bloomier filter: an efficient data structure for static support lookup tables | title = Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms | year = 2004 | pages = 30–39 | url = http://www.ee.technion.ac.il/~ayellet/Ps/nelson.pdf }}
*{{Citation
 | first1 = Saar
 | last1 = Cohen
 | first2 = Yossi
 | last2 = Matias
 | contribution = Spectral Bloom Filters
 | title = Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data
 | year = 2003
 | doi = 10.1145/872757.872787
 | pages = 241–252
 | url = https://whiteblock.io/wp-content/uploads/2019/10/sbf-sigmod-03.pdf
 | isbn = 978-1581136340
 | s2cid = 1058187
 }}
*{{Citation | first1 = Fan | last1 = Deng | first2 = Davood | last2 = Rafiei | contribution = Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters | title = Proceedings of the ACM SIGMOD Conference | year = 2006 | pages = 25–36 | url = http://webdocs.cs.ualberta.ca/~drafiei/papers/DupDet06Sigmod.pdf }}
*{{Citation 
 |first1=Sarang 
 |last1=Dharmapurikar 
 |first2=Haoyu 
 |last2=Song 
 |first3=Jonathan 
 |last3=Turner 
 |first4=John 
 |last4=Lockwood 
 |contribution=Fast packet classification using Bloom filters 
 |title=Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems 
 |year=2006 
 |pages=61–70 
 |doi=10.1145/1185347.1185356 
 |url=http://www.arl.wustl.edu/~sarang/ancs6819-dharmapurikar.pdf 
 |isbn=978-1595935809 
 |url-status=dead 
 |archive-url=https://web.archive.org/web/20070202202510/http://www.arl.wustl.edu/~sarang/ancs6819-dharmapurikar.pdf 
 |archive-date=2007-02-02 
 |citeseerx=10.1.1.78.9584 
 |s2cid=7848110 
 }}
*{{citation
 | last1 = Dietzfelbinger | first1 = Martin
 | editor1-last = Aceto | editor1-first = Luca
 | editor2-last = Damgård | editor2-first = Ivan
 | editor3-last = Goldberg | editor3-first = Leslie Ann
 | editor4-last = Halldórsson | editor4-first = Magnús M.
 | editor5-last = Ingólfsdóttir | editor5-first = Anna
 | editor6-last = Walukiewicz | editor6-first = Igor
 | arxiv = 0803.3693
 | contribution = Succinct data structures for retrieval and approximate membership
 | doi = 10.1007/978-3-540-70575-8_32
 | pages = 385–396
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008, Proceedings, Part I, Track A: Algorithms, Automata, Complexity, and Games
 | volume = 5125
 | year = 2008| isbn = 978-3-540-70574-1
 | s2cid = 1699996
 }}
*{{Citation
 | first1 = Peter C.
 | last1 = Dillinger
 | first2 = Panagiotis
 | last2 = Manolios
 | contribution = Fast and Accurate Bitstate Verification for SPIN
 | title = Proceedings of the 11th International Spin Workshop on Model Checking Software
 | publisher = Springer-Verlag, Lecture Notes in Computer Science 2989
 | year = 2004a
 | url = http://www.ccs.neu.edu/home/pete/research/spin-3spin.html
 }}
*{{Citation
 | first1 = Peter C.
 | last1 = Dillinger
 | first2 = Panagiotis
 | last2 = Manolios
 | contribution = Bloom Filters in Probabilistic Verification
 | title = Proceedings of the 5th International Conference on Formal Methods in Computer-Aided Design
 | publisher = Springer-Verlag, Lecture Notes in Computer Science 3312
 | year = 2004b
 | url = http://www.ccs.neu.edu/home/pete/research/bloom-filters-verification.html
 }}
*{{Citation 
 |first1=Benoit 
 |last1=Donnet 
 |first2=Bruno 
 |last2=Baynat 
 |first3=Timur 
 |last3=Friedman 
 |contribution=Retouched Bloom Filters: Allowing Networked Applications to Flexibly Trade Off False Positives Against False Negatives 
 |title=CoNEXT 06 – 2nd Conference on Future Networking Technologies 
 |year=2006 
 |url=http://www.adetti.iscte.pt/events/CONEXT06/Conext06_Proceedings/papers/13.html 
 |url-status=dead 
 |archive-url=https://web.archive.org/web/20090517023058/http://adetti.iscte.pt/events/CONEXT06/Conext06_Proceedings/papers/13.html 
 |archive-date=2009-05-17 
 }}
*{{Citation
 | contribution = Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters
 | title = Algorithms and Data Structures, 10th International Workshop, WADS 2007
 | publisher = Springer-Verlag
 | series=Lecture Notes in Computer Science
 | volume=4619 | pages = 637–648
 | year = 2007
 | arxiv = 0704.3313
 | bibcode = 2007arXiv0704.3313E
 | title-link = Workshop on Algorithms and Data Structures}}
*{{citation
 | last1 = Fan | first1 = Bin
 | last2 = Andersen | first2 = Dave G.
 | last3 = Kaminsky | first3 = Michael
 | last4 = Mitzenmacher | first4 = Michael D. | title = Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies
 | contribution = Cuckoo filter: Practically better than Bloom
 | doi = 10.1145/2674005.2674994
 | pages = 75–88
 | year = 2014| isbn = 9781450332798
 | doi-access = free
 }}. Open source implementation [https://github.com/efficient/cuckoofilter available on github].
*{{Citation | first1 = Li | last1 = Fan | first2 = Pei | last2 = Cao | first3 = Jussara | last3 = Almeida |  first4 = Andrei | last4 = Broder |  title = Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol | journal = IEEE/ACM Transactions on Networking | volume = 8 | issue = 3 | year = 2000 | pages = 281–293 | doi = 10.1109/90.851975 | url = http://www.ece.eng.wayne.edu/~sjiang/ECE7995-07-fall/slides/summary-cache.pdf | citeseerx = 10.1.1.41.1487 | s2cid = 4779754 | access-date = 2018-07-30 | archive-url = https://web.archive.org/web/20170922002708/http://www.ece.eng.wayne.edu/~sjiang/ECE7995-07-fall/slides/summary-cache.pdf | archive-date = 2017-09-22 | url-status = dead }}. A preliminary version appeared at SIGCOMM '98.
*{{Citation
 | first1 = Ashish
 | last1 = Goel
 | first2 = Pankaj
 | last2 = Gupta
 | title = Small subset queries and bloom filters using ternary associative memories, with applications
 | journal = ACM SIGMETRICS Performance Evaluation Review
 | volume = 38
 | page = 143
 | year = 2010
 | doi = 10.1145/1811099.1811056
 | url = http://www.stanford.edu/~ashishg/papers/inverted.pdf
 | citeseerx = 10.1.1.296.6513
 }}
*{{Citation
 | first1 = Thomas Mueller | last1 = Graf
 | first2 = Daniel | last2 = Lemire
 | title = Xor Filters
 | journal = ACM Journal of Experimental Algorithmics
 | year = 2020
 | volume = 25
 | pages = 1–16
 | doi = 10.1145/3376122
 | arxiv = 1912.08258
 | bibcode = 2019arXiv191208258M
 | s2cid = 209405019
 }}
*{{Citation
| first1 = Fabio
| last1 = Grandi
| title = On the analysis of Bloom filters
| journal = Information Processing Letters
| volume = 129
| year = 2018
| doi = 10.1016/j.ipl.2017.09.004
| url = http://www-db.disi.unibo.it/~fgrandi/papers/IPL2017_accepted.pdf
| pages = 35–39
}}
*{{Citation
 | first1 = Adam
 | last1 = Kirsch
 | first2 = Michael
 | last2 = Mitzenmacher
 | contribution = Less Hashing, Same Performance: Building a Better Bloom Filter
 | title = Algorithms – ESA 2006, 14th Annual European Symposium
 | publisher = Springer-Verlag, Lecture Notes in Computer Science 4168
 | year = 2006
 | pages = 456–467
 | doi = 10.1007/11841036
 | url = http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf
 | volume = 4168
 | editor1-last = Azar
 | editor1-first = Yossi
 | editor2-last = Erlebach
 | editor2-first = Thomas
 | series = Lecture Notes in Computer Science
 | isbn = 978-3-540-38875-3
 | url-status = dead
 | archive-url = https://web.archive.org/web/20090131053735/http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf
 | archive-date = 2009-01-31
 }}
*{{Citation
 | first1 = Y. | last1 = Koucheryavy
 | first2 = G. | last2 = Giambene
 | first3 = D. | last3 = Staehle
 | first4 = F. | last4 =Barcelo-Arroyo
 | first5 = T. | last5 = Braun
 | first6 = V. | last6 = Siris
 | title = Traffic and QoS Management in Wireless Multimedia Networks
 | journal = COST 290 Final Report
 | year = 2009
 | doi = <!-- XVI, 312 -->
 | page = 111}}
*{{Citation
 | first1 = J.
 | last1 = Kubiatowicz
 | first2 = D.
 | last2 = Bindel
 | first3 = Y.
 | last3 = Czerwinski
 | first4 = S.
 | last4 = Geels
 | first5 = D.
 | last5 = Eaton
 | first6 = R.
 | last6 = Gummadi
 | first7 = S.
 | last7 = Rhea
 | first8 = H.
 | last8 = Weatherspoon
 | first9 = W.
 | last9 = Weimer
 | display-authors = 8
 | title = Oceanstore: An architecture for global-scale persistent storage
 | journal = ACM SIGPLAN Notices
 | year = 2000
 | doi = <!-- 2000, VOL 35; PART 11 -->
 | url = http://ftp.csd.uwo.ca/courses/CS9843b/papers/OceanStore.pdf
 | pages = 190–201
 | access-date = 2011-12-01
 | archive-url = https://web.archive.org/web/20120311063707/http://ftp.csd.uwo.ca/courses/CS9843b/papers/OceanStore.pdf
 | archive-date = 2012-03-11
 | url-status = dead
 }}
*{{citation
 | last1 = Maggs
 | first1 = Bruce M.
 | last2 = Sitaraman
 | first2 = Ramesh K.
 | date = July 2015
 | doi = 10.1145/2805789.2805800
 | issue = 3
 | journal = SIGCOMM Computer Communication Review
 | pages = 52–66
 | title = Algorithmic nuggets in content delivery
 | volume = 45
 | url = https://www.akamai.com/us/en/multimedia/documents/technical-publication/algorithmic-nuggets-in-content-delivery-technical-publication.pdf
 | url-status = dead
 | archive-url = https://web.archive.org/web/20210814193152/https://www.akamai.com/us/en/multimedia/documents/technical-publication/algorithmic-nuggets-in-content-delivery-technical-publication.pdf
 | archive-date = 2021-08-14
 | citeseerx = 10.1.1.696.9236
 | s2cid = 65760
 }}
*{{Citation
| publisher = Cambridge University Press
| last1 = Mitzenmacher
| first1 = Michael
| last2 = Upfal
| first2 = Eli
| title = Probability and computing: Randomized algorithms and probabilistic analysis
| year = 2005
| url = https://books.google.com/books?id=0bAYl6d7hvkC&pg=PA110
| pages = 107–112
| isbn = 9780521835404
}}
*{{Citation
 | first1 = Christian Worm | last1 = Mortensen
 | contribution = On dynamic range reporting in one dimension
 | title = Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing
 | year = 2005 | pages = 104–111 | doi = 10.1145/1060590.1060606
 | isbn = 978-1581139600| arxiv = cs/0502032| s2cid = 56473
 }}
*{{Citation
| volume = 16
| issue = 5
| pages = 558–560
| last = Mullin
| first = James K.
| title = Optimal semijoins for distributed database systems
| journal = IEEE Transactions on Software Engineering
| year = 1990
| doi=10.1109/32.52778
}}
*{{Citation
 | first1 = Anna
 | last1 = Pagh
 | first2 = Rasmus
 | last2 = Pagh
 | first3 = S. Srinivasa
 | last3 = Rao
 | contribution = An optimal Bloom filter replacement
 | title = Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
 | year = 2005
 | pages = 823–829
 | url = https://www.itu.dk/people/pagh/papers/bloom.pdf
 }}
*{{citation
 | last1 = Palmieri| first1 = Paolo
 | last2 = Calderoni | first2 = Luca
 | last3 = Maio | first3 = Dario
 | contribution = Spatial Bloom Filters: Enabling Privacy in Location-Aware Applications
 | title = Proc. 10th International Conference on Information Security and Cryptology (Inscrypt 2014)
 | publisher = Springer-Verlag, Lecture Notes in Computer Science
 | pages = 16–36
 | volume = 8957
 | year = 2014
 | doi = 10.1007/978-3-319-16745-9_2
 | isbn = 978-3-319-16744-2
 | citeseerx = 10.1.1.471.4759
 }}
*{{citation
 | last = Porat | first = Ely
 | editor1-last = Frid | editor1-first = Anna E.
 | editor2-last = Morozov | editor2-first = Andrey
 | editor3-last = Rybalchenko | editor3-first = Andrey
 | editor4-last = Wagner | editor4-first = Klaus W.
 | arxiv = 0804.1845
 | contribution = An optimal Bloom filter replacement based on matrix solving
 | doi = 10.1007/978-3-642-03351-3_25
 | pages = 263–273
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Computer Science, Theory and Applications: Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18–23, 2009, Proceedings
 | volume = 5675
 | year = 2009| isbn = 978-3-642-03350-6
 | s2cid = 3205108
 }}
*{{Citation
 | first1 = E. | last1 = Pournaras
 | first2 = M. | last2 = Warnier
 | title = A generic and adaptive aggregation service for large-scale decentralized networks
 | journal = Complex Adaptive Systems Modeling
 | year = 2013
 | volume = 1
 | issue = 19
 | page = 19
 | doi = 10.1186/2194-3206-1-19| doi-access = free
 }}. Prototype implementation [https://github.com/epournaras/DIAS available on github].
*{{Citation
 | first1 = F.
 | last1 = Putze
 | first2 = P.
 | last2 = Sanders
 | first3 = J.
 | last3 = Singler
 | contribution = Cache-, Hash- and Space-Efficient Bloom Filters
 | title = Experimental Algorithms, 6th International Workshop, WEA 2007
 | publisher = Springer-Verlag, Lecture Notes in Computer Science 4525
 | year = 2007
 | pages = 108–121
 | doi = 10.1007/978-3-540-72845-0
 | url = http://algo2.iti.uni-karlsruhe.de/singler/publications/cacheefficientbloomfilters-wea2007.pdf
 | volume = 4525
 | editor1-last = Demetrescu
 | editor1-first = Camil
 | series = Lecture Notes in Computer Science
 | isbn = 978-3-540-72844-3
 | access-date = 2007-07-18
 | archive-date = 2007-06-23
 | archive-url = https://web.archive.org/web/20070623102632/http://algo2.iti.uni-karlsruhe.de/singler/publications/cacheefficientbloomfilters-wea2007.pdf
 | url-status = dead
 }}
*{{Citation
 | first1 = Ori
 | last1 = Rottenstreich
 | first2 = Yossi
 | last2 = Kanizo
 | first3 = Isaac
 | last3 = Keslassy
 | contribution = The Variable-Increment Counting Bloom Filter
 | title = 31st Annual IEEE International Conference on Computer Communications, 2012, Infocom 2012
 | year = 2012
 | pages = 1880–1888
 | doi = 10.1109/INFCOM.2012.6195563
 | url = http://webee.technion.ac.il/~isaac/p/infocom12_variable.pdf
 | isbn = 978-1-4673-0773-4
 | citeseerx = 10.1.1.174.7165
 }}
*{{Citation 
 |first1=Simha 
 |last1=Sethumadhavan 
 |first2=Rajagopalan 
 |last2=Desikan 
 |first3=Doug 
 |last3=Burger 
 |first4=Charles R. 
 |last4=Moore 
 |first5=Stephen W. 
 |last5=Keckler 
 |contribution=Scalable hardware memory disambiguation for high ILP processors 
 |title=36th Annual IEEE/ACM International Symposium on Microarchitecture, 2003, MICRO-36 
 |year=2003 
 |pages=399–410 
 |doi=10.1109/MICRO.2003.1253244 
 |url=http://www.cs.utexas.edu/users/simha/publications/lsq.pdf 
 |isbn=978-0-7695-2043-8 
 |url-status=dead 
 |archive-url=https://web.archive.org/web/20070114035556/http://www.cs.utexas.edu/users/simha/publications/lsq.pdf 
 |archive-date=2007-01-14 
 |citeseerx=10.1.1.229.1254 
 |s2cid=195881068 
 }}
*{{Citation
 | first1 = David
 | last1 = Starobinski
 | first2 = Ari
 | last2 = Trachtenberg
 | first3 = Sachin
 | last3 = Agarwal
 | title = Efficient PDA Synchronization
 | journal = IEEE Transactions on Mobile Computing
 | volume = 2
 | year = 2003
 | doi = 10.1109/TMC.2003.1195150
 | page = 40
 | issue = 1
 | url = http://people.bu.edu/staro/efficient_pda.pdf
 | citeseerx = 10.1.1.71.7833
 }}
*{{Citation
 | first1 = Ulrich | last1 = Stern
 | first2 = David L. | last2 = Dill
 | contribution = A New Scheme for Memory-Efficient Probabilistic Verification
 | title = Proceedings of Formal Description Techniques for Distributed Systems and Communication Protocols, and Protocol Specification, Testing, and Verification: IFIP TC6/WG6.1 Joint International Conference
 | publisher = Chapman & Hall, IFIP Conference Proceedings
 | year = 1996
 | citeseerx = 10.1.1.47.4101
 | pages = 333–348}}
*{{Citation
| first1=S. Joshua| last1 = Swamidass
| title=Mathematical correction for fingerprint similarity measures to improve chemical retrieval| journal=Journal of Chemical Information and Modeling| year=2007| volume=47| number=3| pages=952–964| pmid = 17444629| doi=10.1021/ci600526a}}
*{{Citation| last=Wessels | first=Duane |date=January 2004 | chapter=10.7 Cache Digests | title=Squid: The Definitive Guide | edition=1st | publisher=O'Reilly Media | isbn=978-0-596-00162-9 | page=172 | quote=Cache Digests are based on a technique first published by Pei Cao, called Summary Cache. The fundamental idea is to use a Bloom filter to represent the cache contents.}}
*{{citation
 | last1 = Tarkoma
 | first1 = Sasu
 | last2 = Rothenberg
 | first2 = Christian Esteve
 | last3 = Lagerspetz
 | first3 = Eemil
 | contribution = Theory and practice of bloom filters for distributed systems
 | url = https://git.gnunet.org/bibliography.git/plain/docs/TheoryandPracticeBloomFilter2011Tarkoma.pdf
 | pages = 131–155
 | title = IEEE Communications Surveys & Tutorials, no. 1.
 | volume = 14
 | year = 2012
 }}
*{{citation
 | last1 = Zhiwang | first1 = Cen
 | last2 = Jungang | first2 = Xu
 | last3 = Jian | first3 = Sun
 | contribution = A multi-layer Bloom filter for duplicated URL detection
 | doi = 10.1109/ICACTE.2010.5578947
 | pages = V1–586–V1–591
 | title = Proc. 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE 2010)
 | volume = 1
 | year = 2010| isbn = 978-1-4244-6539-2
 | s2cid = 3108985
 }}
{{Refend}}

==External links==
*[http://www.perl.com/pub/2004/04/08/bloom_filters.html "Using Bloom Filters"] Detailed Bloom Filter explanation using [[Perl]]
*[http://www.michaelnielsen.org/ddi/why-bloom-filters-work-the-way-they-do/ Why Bloom filters work the way they do (Michael Nielsen, 2012)]
*[https://www.cs.dal.ca/research/techreports/cs-2002-10 Bloom Filters — A Tutorial, Analysis, and Survey (Blustein & El-Maazawi, 2002)] at Dalhousie University
*[http://www.cs.wisc.edu/~cao/papers/summary-cache/node8.html Table of false-positive rates for different configurations] from a [[Organization:University of Wisconsin–Madison|University of Wisconsin–Madison]] website
*[https://www.youtube.com/watch?v=947gWqwkhu0 "More Optimal Bloom Filters", Ely Porat (Nov/2007) Google TechTalk video] on [[Company:YouTube|YouTube]]

{{DEFAULTSORT:Bloom Filter}}
[[Category:Hashing]]
[[Category:Probabilistic data structures]]
[[Category:Lossy compression algorithms]]

{{Sourceattribution|Bloom filter}}