10 ms·

Bloom filters debunked: Dispelling 30 Years of bad math with Coq

• anonymoushn 6y ago
  Is there a sound technique to get your k hash functions to produce k distinct bits, such that the original derivation would become correct?
  • TheRealPomax 6y ago
    You had me until "such that the original derivation would become correct", which doesn't make a lot of sense?
    • anonymoushn 6y ago
      Oh, you're right. The beginning of the original derivation assumes that the bits chosen by each hash function for a single input are independent (so it does not always produce k distinct bits) but the end assumes that it does produce k distinct bits. So it would still be incorrect. I expect that you would get a lower false-positive rate, though, if some inputs could not randomly query fewer than k bits of the filter!
      • gopiandcode 6y ago
        There are variants of the Bloomfilter that do try and do this - one way is to have each hash function map to a separate distinct subsequence of the bitvector. It does indeed reduce the false positive rate, but comes at the cost of increased space usage. As always, utility of this modification would depend on where you wanted to balance space-vs-accuracy constraints.
        • anonymoushn 6y ago
          I would hope not to use any additional space. A naive approach is to choose 1 bit out of N from the first hash, 1 out of the remaining N-1 from the second hash, and 1 out of the remaining N-2 from the third, and so on.
          • gopiandcode 6y ago
            That would fix the final independence problem, but it would also require further changes to other stages of the proof. For example, this strategy would then mean that when calculating the probability of a single bit being set, the hash outcomes are no longer independent, which means that a different expression would be needed. Additionally, from a practical sense, this variation might also be more costly to execute, as setting bits would go from a single memory access to a linear scan. I think it might be interesting to look into though.
            • anonymoushn 6y ago
              You can decide which bits to set for an input in k^2 time I guess, not k*n time, then set each one with a single memory access.
        • xpe 6y ago
          It is two words: “Bloom filter”.
          • xpe 6y ago
            The original article used "Bloomfilter" instead of "Bloom filter". As of 2020-08-02, some of those mistakes have been corrected. Two mistakes remain.
  • marcan_42 6y ago
    You could just keep hashing until you have enough non-colliding outputs, throwing away any collisions. This is sound as far as I can tell. Relatedly, mapping real hash functions to bits is also nontrivial to get 100% mathematically correct. As far as I know, the only sound way for hash functions with a fixed number of output bits and a non-power-of-two bloom filter is to truncate to the next power of two, then throw away any results that overflow the filter size and keep trying with new hashes (or repeated hashing). This is thus easy to integrate with avoiding duplicate bits, since you're retrying anyway. In practice, none of this matters, you can just take a hash output with enough extra bits modulo the Bloom filter size and call it a day. It'll be close enough to uniformly random and non-colliding anyway, for practical filters.
  • ReaLNero 6y ago
    It's not too difficult: hash function 1 generates an integer from 0 to n-1, that index element is deleted, then hash function 2 generates an integer from 0 to n-2, that element is deleted etc. This is an O(n^2) algorithm, which you can improve to O(nlgn) using fenwick trees. In practice however, it is much quicker to generate random hashes and repeat until they're distinct.
    • anonymoushn 6y ago
      In k^2 time, which is maybe faster than running a hash an additional time: function get_bits(input, hashes, n) local bits = {} for i=1,#hashes do local bit = hashes[i](input) % (n-i+1) for j=1,i-1 do if bits[j] <= bit then bit = bit + 1 end end bits[i] = bit while i > 1 and bits[i] < bits[i-1] do bits[i], bits[i-1] = bits[i-1], bits[i] i = i - 1 end end return bits end
      • marcan_42 6y ago
        Your % operation is not uniformly distributed if the hash domain isn't an integer multiple of the output size, which is a bigger problem for formal correctness than the colliding output issue (hashes are not uniformly distributed). You need to truncate to an even number of bits and retry until the output is < n, at which point you're retrying anyway, so you can just retry on collision instead of having all that complicated logic to skip bits. Nice try though, but if you want formally perfect results like the OP you have to try harder :-) (except real hash functions are only assumed to have perfectly distributed functions anyway, that is not proven and probably not provable, so basically you're screwed either way and none of this matters :-) ).
  • contravariant 6y ago
    There's always the combinatorial number system. But it might be more effort than it's worth. As others have pointed out you can also just make the k^th hash pick any of the n-k remaining options.
• bawolff 6y ago
  This is important work and all, but i can't help but feel the headline is a bit clickbaity
  • gopiandcode 6y ago
    Yes, that's a fair comment. I took some creative liberties with the title to try and make this theoretical result more relatable to the average reader, but it's possible I may have gone too far.
    • random314 6y ago
      It would be interesting if you can show how Coq refused to accept the old formula and what error it produced.
      • gopiandcode 6y ago
        When I was attempting to prove Bloom's original incorrect bound, the work never progressed to the point where I was actively working directly on proving his bound - I managed to prove some intermediate theorems, but was unable to work out a way to compose them. The issue ended up being that that I was unable to derive the independence required to prove the inductive step. If you're interested at looking at the sources, I think the following commit was around the place where I was working on this: https://github.com/certichain/ceramist/commit/70927c5b50e21a08f510cfd9555d8324a61c1233 https://github.com/certichain/ceramist/commit/70927c5b50e21a...
      • jhanschoo 6y ago
        Note that you don't really "get <a proof assistant> to refuse to accept" an incorrect result, you just fail to construct a proof for it, as the author talks about in their reply. What you can do, sometimes, is succeed in proving the negation of the incorrect result.
    • ImaCake 6y ago
      As someone totally unaware of bloom filters, I appreciate the click bait title because it made me aware of them, and then almost immediately understand what they are thanks to the clear explanation and visuals :)
• mdonahoe 6y ago
  “ To be fair, the asymptotic behaviour of Bloom's original bound is consistent with this updated definition, so the impact is more on an issue of pedantry rather than for practical applications.” Would love to see a table with computed numbers comparing the rates. It’s hard for me to understand the behavior of that second result
  • gopiandcode 6y ago
    This paper[1] which corrected Bose et al.'s original derivation, has more discussion about the impact of the second result - in particular, Figure 2 (on page 13) has a comparison of the relative error of the old and new bounds against the empirically calculated rate. [1] https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=903775 https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=90377...
• jchw 6y ago
  A bit tangential, but I suspect many people don’t know is there is actually more information-dense data structures for the use case of bloom filters; Cuckoo filters for example can get close to the theoretical lower bound of information required and have some other interesting properties. So you should consider that before reaching for bloom filters, probably!
  • haecceity 6y ago
    Bloom filter was probably chosen not because of its false negative rate but because it was good enough whatever its false negative rate is.
    • jchw 6y ago
      I'd guess bloom filters were often chosen because it was one of the only available options. I believe cuckoo filters were invented in 2014.
    • eis 6y ago
      Bloom filters have no false negatives, they have only false positives. If it were the other way round, they would be of no practical use as you'd have to query the original datastructure in any case: - If the bloom filter said "True", then you go ahead and fetch the data from the original structure - If the bloom filter said "False" but that might be a false negative then you'd have to anyway query the original structure to be sure With 0% false negatives but a relatively small rate of false positives instead, you don't have to query the original source if the filter gave a "False". Btw. Bloom filters were one of the first probabilistic data structures with real practical uses and still to this day are widely used. They are still not out-classed in every way by newer algorithms like Cuckoo filters.
      • ImaCake 6y ago
        To clarify why this is the case. It is because bloom filters effectively group everything in set X that you want to check for into a much smaller "approximated set" (the bit-vector). You can then check elements of set Y against the approximated set as a much faster test of whether they are in set X. The important detail here is that the approximated set will be positive for anything that matches an item in set X plus some additional items that are not in set X.
• thomasahle 6y ago
  The original false negative rate approximation can be proved (correctly) using Martingale arguments as done by Mitzenmacher and Upfal in 2005. The Wikipedia page also shows this version.
  • gopiandcode 6y ago
    Ah, that's a new change on the wikipedia page, when I started work on this proof back in December, the Wikipedia page actually had the incorrect derivation. Additionally, Bloom's original bound is given (and typically quoted) as an exact expression for the false positive rate, so while it may be correct as an approximation, I'd say its fair to say that the original bound is wrong.
    • thomasahle 6y ago
      Yeah, it's only right asymptotically. It's nice work testing some of those things in coq.
• drewm1980 6y ago
  I'm curious about the properties of the new approximate membership algorithms you discovered as part of this research. Are they better? "We instantiated this interface with each of the previously defined AMQ structures, obtaining the Blocked Bloom filters, Counting Blocked Bloom filters and Blocked Quotient filter along with proofs of similar properties for them, for free." So it sounds like the new AMQ algorithms you allude to are blocked (more cache friendly) variants of existing AMQ algorithms. Are the bounds you proved all good in some sense? Do you know yet if they're actually faster in practice on real hardware, or do optimized implementations still need to be written?
  • gopiandcode 6y ago
    The corresponding bounds for the variant structures we construct do result in lower false-positive rates than a standard Bloomfilter - so, in that sense, you could say that they are better. However, they also require more space, striking a slightly different theoretical trade-off between space and accuracy. For practical purposes, you would have to take the effect of caches into account, and the performance may vary depending on the particular choice of hardware. Our work stuck mainly to the theoretical side, so we didn't do any empirical testing of these new data structures. I guess the jury is still out on whether these variants are actually better in practice than the existing ones.
• yomly 6y ago
  This was very accessible! Thank you for writing it. There were a couple of typos - might be worth getting someone to proof read it... (I am out atm so don't have a good way of laying out suggestions for corrections)
  • gopiandcode 6y ago
    Thanks for the feedback. My main aim with this post was just to provide a slightly more accessible introduction to the full work, so I'm glad that it was successful in that sense. It was mostly just a quick transcription of the corresponding presentation for the paper, so some typos may have crept in. I'll do a second pass and try and fix that later today.
    • yomly 6y ago
      Yes - I didn't know what a bloom filter was but found it very easy to follow along and even anticipate where things were going. The diagrams are great too!
    • PAPPPmAc 6y ago
      That's mostly a really nice explanation, the one thing that bugged me (which is my pet peeve in math-y CS papers) is a not-perfectly-clear explanation of your variables. The ones in the equations interspersed with the diagrams of the original derivation are easy enough to pick up from the diagrams, but you switched from $n$ to $l$ for the number of inputs in the correct expression (and the Bose paper also used $n$, so I'm not sure why).
      • gopiandcode 6y ago
        Thanks for the comment. I think that was actually a mistake in my writeup, I just copied the latex from the paper without adjusting it to the notations used in the article. I'll make sure to fix it.
• reanimus 6y ago
  This is interesting stuff! It's especially nice to see some more details behind the math -- I did some stuff with bloom filters for work and found that the math didn't always seem to line up with what we'd expect during tests. I wonder if it needs some adjustment...
• curryhoward 6y ago
  I feel like most commenters are missing the point. The fact that this issue was finally settled once and for all using a proof assistant is a huge achievement! That's the highest degree of scrutiny that a proof can undergo. This is especially important given the high number of mistakes in prior work—one would be forgiven for distrusting new papers on this topic that don't have machine-certified proofs. I can't believe people think this is just clickbait. Do y'all not recognize the importance of math being...well...correct?
  • zozbot234 6y ago
    It's a nice accomplishment, but even the article footnotes note that getting the definitions right for the paper was as important as verifying the actual proofs. And a proof assistant cannot fully verify your definitions, so these checks are still largely left to human scrutiny.
    • gopiandcode 6y ago
      Just to clarify, Bose et al.'s paper was incorrect due to an incorrect definition of Stirling numbers of the second kind (some of their expressions used the wrong exponents). In our certified work, in light of this error, we ended up deriving the expression for Stirling numbers of the second kind from first principles[1], eliding it as a source of errors. As such, the main definition that needs to be human-verified in our work is the actual implementation of the Bloomfilter[2], which is fairly simple and easy to check as being correct. [1] https://github.com/certichain/ceramist/blob/fd5e522f2c381f7dbd5b8e38b48041dfd4bd261a/Utils/stirling.v#L341 https://github.com/certichain/ceramist/blob/fd5e522f2c381f7d... [2] https://github.com/certichain/ceramist/blob/fd5e522f2c381f7dbd5b8e38b48041dfd4bd261a/Structures/BloomFilter/BloomFilter_Definitions.v#L98 https://github.com/certichain/ceramist/blob/fd5e522f2c381f7d...
  • tom_mellior 6y ago
    The article doesn't say that the original proof was incorrect. It argues that one of the original theorem's assumptions was not justified. A machine certified proof doesn't help with this. [EDIT: The author points out below that the assumption was not explicit in Bloom's work. An attempt at a machine certified proof would catch this aspect. But not the aspect of the assumption being wrong, if it were added explicitly.] Now, others later recognized this faulty assumption and produced a new formula and a faulty proof for its correctness. A machine certified proof would help here if an actual proof step is wrong, except note the footnote: "To be fair, the error in Bose et al.'s paper was primarily due to incorrect definitions, rather than an incorrect logical step. As an interesting anecdote, the first version of our work was based off the incorrect definitions by Bose et al. and ended up being rejected by reviewers who then rediscovered this error." So again it was human checking that (re-)discovered an issue. One that appears to have been fixed by humans before this work. And one that the machine wasn't able to find. So now that all known incorrect assumptions are shaken out (there might be unkown ones, Coq can't tell) this work is a machine checked proof of something that had been proved before. It's an achievement, and it's good to have certainty. Almost anything that gets us closer to more formal math and computer science is good. But this particular result is hardly spectacular. As for the clickbait aspect, I'm also annoyed by it. The title is clearly factually incorrect. No property of Bloom filters has been debunked. A widely cited formula was replaced by an asymptotically equivalent one 12 years ago, and we now have a machine checked argument that this replacement was correct. This isn't a debunking of anything. No math has been disspelled. Clear and honest science communication is important. Authors overselling their work in such (obvious) ways just highlights that they themselves don't think the work is sensational (which it doesn't have to be!), and it makes readers wonder in what other ways they are intellectually dishonest.
• peter_d_sherman 6y ago
  >"Using a probabilistic data structure known as a Bloomfilter, Browsers maintain a approximate representation of the set of known malicious URLs locally. By querying this space-efficient local set, browsers will only send up a small proportion of URLs that have a high likelihood of actually being malicious."
• ghj 6y ago
  The theory of hashing never matched up well with how I've experienced it in the real world. For example almost all analysis of the hash table (for proving stuff about load factor, chain length, or probe clustering sizes, etc) starts off with a "uniform hashing" assumption. But that assumption have basically never held true given how languages define their default hashes.
• layoutIfNeeded 6y ago
  It’s not “Bloomfilter” but “Bloom filter” after Burton Howard Bloom.
  • gopiandcode 6y ago
    My bad, I didn't realize, I will update the post accordingly.
• NikkiA 6y ago
  Surely the original 'false positive rate' is only wrong if the hash function is 'bad', and thus Bloom wasn't 'incorrect' as much as assuming a perfect hash function.
  • gopiandcode 6y ago
    I don't think that would solve this issue - a perfect hash function is guaranteed to not have any collisions for any element in some predefined set. What Bloom's proof requires is that all of the k hash functions should not have any collision for any input that is inserted into the Bloom filter, which is not covered by just having each function alone be perfect. That aside, Bloom does not make any assumptions about the chosen hash functions being perfect or not.
    • jesboat 6y ago
      Correct. In the extreme case, imagine that your k hash functions are nearly identical: hash function `H_i` differs from `H_1` only in that the outputs for the `1`st and `i`th elements in the input space are swapped. Of the `N` elements in the input space, all but `k` will completely collide.
  • Dylan16807 6y ago
    Assuming a perfect hash function (or similar) out of nowhere is a crazy thing to do, and solidly incorrect in my book. If you could assume a perfect hash function, you could treat 64 or 80 bits as secure in a wide swath of inappropriate contexts.
    • a1369209993 6y ago
      > you could treat 64 or 80 bits as secure You're confusing statistically uniform with cryptanalytically secure. By that logic you can 'debunk' plain old hash tables because someone might feed you keys that all hash to the same slot.
      • Dylan16807 6y ago
• ur-whale 6y ago
  The actual Coq code is here: https://github.com/certichain/ceramist/blob/fd5e522f2c381f7dbd5b8e38b48041dfd4bd261a/Structures/BloomFilter/BloomFilter_Probability.v#L1187 https://github.com/certichain/ceramist/blob/fd5e522f2c381f7d...
• hyyypr 6y ago
  > Conversely, sending every URL that a user visits to some external service, where it could be logged and data-mined by nefarious third parties (i.e Google) As in, just like DNS.
  • dan-robertson 6y ago
    DNS sends only the domain name and you can choose who your DNS resolvers will be
  • rrdharan 6y ago
    Google was also the one that invented the technique to prevent sending the URLs serverside. So the random potshot feels unwarranted.
    • sukilot 6y ago
      It's a shame that the OP went to huge effort to make a mathematically perfect proof, and that wrote such a deceptive article about it. It's an ironic demonstration that we shouldn't trust prose. The author's implied thesis is that papers are worthless and only code matters, which applied to the author's paper too!
      • gopiandcode 6y ago
        Apologies if the article came off as deceptive, my intentions were not to try and mislead anyone. While the result may not have practical implications, I don't think that the "debunked" part of the story is incorrect. To reiterate a point I made in an earlier response: In the paper, we actually present a large number of other papers in the literature (even some recent as 2019) that actually still incorrectly refer to Bloom's expression as an exact bound, so I do think that this is important and somewhat justifies the debunked narrative.
        • tantalor 6y ago
          You should remove the unwarranted "nefarious" slam. It's simply incorrect; the actual reason the browser does not send the URL to a central service is user's expectations of privacy do not allow their browsing history to be logged like that, even if the purpose is for malware protection. They have not given proper informed consent, and fortunately don't need to in order to detect malware. From "Google Chrome Privacy Whitepaper": Chrome checks the URL of each site you visit or file you download against this local list. If you navigate to a URL that appears on the list, Chrome sends a partial URL fingerprint (the first 32 bits of a SHA-256 hash of the URL) to Google for verification that the URL is indeed dangerous. Chrome also sends a partial URL fingerprint when a site requests a potentially dangerous permission, so that Google can protect you if the site is malicious. Google cannot determine the actual URL from this information. https://www.google.com/chrome/privacy/whitepaper.html#malware https://www.google.com/chrome/privacy/whitepaper.html#malwar... (I work for Google but not on anything like this.)
• Kenji 6y ago
  Why not just download all the offending URLs? "Millions and millions" of entries are nothing for a modern computer. That's a couple of megabytes, and you can heavily compress it. Size-wise, it would be on the order of magnitude of visiting this website. And once you have it, you only need diffs. And querying the data set could be done with a simple binary search, requiring no more than log_2(1000000) steps, which is roughly 20.
• gregw2 6y ago
  I thought the article had a very nice, succinct and clear explanation of bloom filters and wanted to say thanks to the author reading this thread. A year or two ago when bloom filters became a recurring popular topic on HN I read a long illustrated medium post on them found via HN out of curiosity to add the concept and tool to my back pocket, and it all seemed complicated and the explanation didn't stick. Your explanation however was quick and made complete sense and I cannot forget it. Appreciate it! Thank you!
  • rkangel 6y ago
    I agree. This article finally resulted in me grokking how the k hash functions actually work together.
  • ImaCake 6y ago
    Yeah the visual really helps with explaining the concept. I read the wiki article on bloom filters first, which was great for understanding the motivation for a bloom filter, but I subtly mis-interpreted how the hash functions were used to set the bit-vector. The visuals in the linked post clarified this really succintly.
  • tomxor 6y ago
    Agree, it almost highlights how bad others descriptions can be sometimes. I mean the article makes it feel like such a simple idea given how many words are spoken about it. I wonder if the key is in quickly grounding the core abstractions with concrete meaning early on, that way your mind quickly has a model of "things" to operate on before attempting to build up the behaviour with more abstract description. Many descriptions stay in the abstract too long without anything to attach it to for the uninitiated... in which case you either persevere and eventually it clicks and all the relationships fall into place - or you give up out of disinterest. I've noticed this when explaining things to others, especially non-technical people, when explaining seemingly very simple things, attempting to describe them in multiple ways and failing, and then realizing they need clarification of the "what", after which explanation is easy - sometimes you are blind to it when you already know "what" and already have the mental model so you jump straight into how and why.
  • 6y ago
• hanoz 6y ago
  I can't follow all the maths but the introduction is surely wrong based on simple probability alone. It's claimed that the URLs which browsers send up (having been diagnosed positive by the test) will ”have a high likelihood of actually being malicious", but that by no means follows from the test's low false positive rate. You need to consider the background rate. Just like in the classic example of a positive diagnosis from a low false positive test for a rare desease.
  • gopiandcode 6y ago
    I think in this case the fact that there are no false negatives means that the low false positive rate is enough to infer that a positive result implies high likelihood of actually being malicious. You can reason roughly as follows: P[ pos | mal ] = 1 (no false negatives) = P[ pos /\ mal ] = P[ mal ] (Bayes) A low false positive rate means that: P[ pos | ¬ mal ] ~= 0 (low false positive rate) P[ pos /\ ¬ mal ] / P[ ¬ mal ] ~= 0 (P[ pos ] - P[ pos /\ mal])/(1 - P[mal]) ~= 0 (P[ pos ] - P[ mal ])/(1 - P[ mal ]) ~= 0 From this fraction we can conclude: P[ pos ] - P[ mal ] ~= 0 Returning back to a the likelihood of being malicious given a positive result: P[ mal | pos ] = P[ mal /\ pos ] / P[pos] = P[ mal ] / P[ pos ] ~= 1.0
    • hanoz 6y ago
      I think you're right. I'll stick to the day job.
      • sukilot 6y ago
        No, you were right, and OP was wrong.
      • hanoz 6y ago
        No, wait, I think I was right after all. Say we have a million urls, and a thousand of them are malicious. Our filter returns a positive result for all the malicious 1000 (no false negatives) and for the safe 999000 urls only 1% will return positive (low false positive), but that's still 9900 false positives. So a positive result only has a (1000 / (1000 + 9900)), i.e. 9%, chance of actually being malicious. Even with a false positive result of only 0.1%, the probability of a positive result actually being malicious only rises to 50%, so still not in "high likelihood" territory.
• fierarul 6y ago
  For an academic paper this page was extremely engaging! Congrats to the author.
• dan-robertson 6y ago
  Here’s a derivation of the formula Bose et al give for the false positive probability: To calculate the probability, we will work out the number of ways to assign kl hashes to m bits (I.e. functions from a set of size kl to a set of size m), and for each of those ways we will work out how many ways we could assign k hashes to the bits which are set (I.e. ways to get a false positive). We then count the number of possible ways to assign our kl hashes of existing elements and k hashes of the tested element to m bits and divide the former by the latter. For the argument to be valid, each assignment of hashes to bits must have equal probability, which is true if the hashes are independent. The simple way to count the number of assignments of kl hashes to m bits is easy: for each hash there are m possible bits so we get: m^(kl) Similarly for kl + k hashes: m^(k(l + 1)) Now we will break this count up by the number of bits which are set. Suppose i bits are set. Then the number of possibilities for those set bits of the m total bits is (m choose i). And the number of ways the kl hashes could be assigned to the i bits is equal to the number of surjections from a set of kl hashes to a set of i bits, which is i!{kl; i}, where {s; t} is the sterling number of the second kind, the number of ways to partition s labelled objects into t unlabelled non-empty partitions [the author’s paper claims this is the number of surjections which is slightly wrong]. This gives the number of assignments given exactly i set bits as: (m choose i) i! {kl; i} And the total as: m^(kl) = Sum_(i = 0)^m (m choose i) i! {kl; i} Given exactly i bits are set, how many ways can we assign k hashes to those i bits? Easy: i^k. So the number of lists of kl + k hashes (integers from 1 to m) such that the last k all appear in the earlier list of kl is: Sum_i i^k (m choose i) i! {kl; i} Finally we divide by the number of possible lists, m^(k(l+1)), to get the probability given by Bose et al (this is valid because the hashes are iid so each list has equal probability of occurring)
• martincmartin 6y ago
  The new formula doesn't appear in the Wikipedia article for Bloom Filter, although it does say that the old formula is only an approximation because of the incorrect independence assumption.
• cb321 6y ago
  It bears mentioning that not only cuckoo filters but also simply vanilla linear probed hash tables of B-bit truncated hashes (sometimes called fingerprints) can be a better substitute for Bloom filters. This seems a highly under propagated fact. "high p" (order 10%) numerical examples are often used to sell an idea less valuable at small p. An (asymptotic, for p <=~ 10%) back of the envelope formula is that such a hash table/set of fingerprints takes up a factor of about (1+log_{1/p}(N)) more space than a Bloom filter. It is not hard to derive this. Unlike the incredibly precise Coq formula proof theme, this is all approximate, but more engineering-relevant. If you were targeting p=0.001 to have a small mistake rate, 1 + log_1000(N) is pretty small (say <~ 1+3=4 for for N <~ 1e9 elements). While it does use 25% space, this Bloom filter would require many more (-log_2(p) =~ 10) probes while the LP hash table would only hit the DIMMs once. Many, but not all, might view a 10x latency reduction as worth 4x the space in the game of space-speed trade-offs.
  • cb321 6y ago
    I should also have said that this competing idea was raised literally in the very same Burton Bloom 1970 paper that the more famous filters come from. Analysis of speed these days (where a single main memory hit is thousands of superscalar dynamic instructions) is tilted differently than it was in 1969. Still, even back then Bloom's own original paper had a footnote qualifying his superiority conclusion as dependent upon memory system assumptions. Beats me how this gets lost. Call it "The Bloom filter mystique".
• dooglius 6y ago
  I didn't realize Bloom filters were used in this way. Thinking adversarially for a moment, doesn't this provide an easy way to get a target website marked as a false positive?
  • advance512 6y ago
    After a positive result is returned for a URL, a verification is done with Google's servers to see the positive is not a false positive.
  • a1369209993 6y ago
    Thinking more adversarially, doesn't this provide an easy way to track anyone who visits a target website?
    • dooglius 6y ago
      Based on advance512's answer, it sounds that way.
• natch 6y ago
  Their prose description of a bloom filter firstly has a significant flaw, and secondly falls victim to what I believe is a fallacy in many discussions about bloom filters. The flaw is that they do not specify that the size of the bit array should be a prime number. This omission alone is astounding. To be fair, they state that they assume the bits from the hash functions are randomly distributed over the bit vector, so with this assumption they skate past this issue even though they have apparently missed that crucial detail of part of how it is accomplished. One wonders if they were unaware. The fallacy imho, but this is where I depart from the community, thus imho, so take me with a grain of salt if you wish, is that you don’t need multiple independent hash functions. You just need multiple inputs. For example instead of hashing the word “salad” three times, just hash the tokens salad1, salad2, and salad3. If your hash function is worth its salt (npi) then you will be just fine.
  • gopiandcode 6y ago
    This is a good point about practical implementations of hashing based randomization - incorrect table sizes can invalidate assumptions about uniformity and cause guarantees to fail. However, this work was primarily about the theoretical analysis of these data structures, which presupposes that we already have a means of generating uniformly randomly distributed bits over the table space, hence the lack of discussion about table sizes.
• phkahler 6y ago
  What if a distinct bit vector is used for each hash function? Then isn't the original false positive rate correct? Can you use less storage by having distinct bit vectors of each hash? This seems like a natural question once we know the false positive rates are different. Maybe Bloom was misinterpreted and right all along?
  • gopiandcode 6y ago
    Good point, You are right that our correction does not address errors in Bloom's original definition of a Bloom filter - which uses distinct bit vectors, but rather in the definition of the Bloom filter that is typically used (and referenced) in practice (Knuth's version) and in the literature, which functions in the way described in the article. This version is easier to implement as the hash functions are independent, but which does use incorrect reasoning in it's correctness proof. It's wrong to attribute this to Bloom, so I've added a note to address this.