3
$\begingroup$

I need to create a bloom filter of 208 million URLs. What would be a good choice of bit vector size and number of hash functions? I tried a bit vector of size 1 GB and 4 hash functions, but it resulted in too many false positives while reading.

I have a huge web corpus containing web content of billions of URLs. I need to process the web content of URLs satisfying certain criteria: the URL should have appeared in web search results in the past 7 days at least 5 times. This is represented by a list of 208 million URLs. Joining the list directly with the web corpus is not feasible because of volume. So I am considering creation of a bloom filter out of the list and then using the bloom filter to prune out unnecessary URLs from the web corpus.

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ Hard to say as you haven't told us your goals etc, making this open ended. You best bet is to experiment. $\endgroup$
    – Aryabhata
    Commented Sep 19, 2012 at 17:58
  • $\begingroup$ @AryaBhata I have a huge web corpus containing web content of billions of URLs. I need to process the web content of URLs satisfying certain criteria (and this is represented by a list of 208 million URLs). Joining the list directly with the web corpus is not feasible because of volume. So I am considering creation of a bloom filter out of the list and then using the bloom filter to prune out unnecessary URLs from the web corpus. $\endgroup$
    – Aadith Ramia
    Commented Sep 19, 2012 at 19:05
  • $\begingroup$ Can you go deeper into the specifics? Like what is actually the criterion? $\endgroup$
    – Aryabhata
    Commented Sep 20, 2012 at 3:10
  • $\begingroup$ Criterion - the URL should have appeared in web search results in the past 7 days at least 5 times $\endgroup$
    – Aadith Ramia
    Commented Sep 20, 2012 at 9:54
  • $\begingroup$ Why don't you edit the question with whatever details you can provide? Perhaps give an example of how you intend to use the bloom filter. $\endgroup$
    – Aryabhata
    Commented Sep 20, 2012 at 15:21

2 Answers 2

Reset to default
6
$\begingroup$

Using the formula from wikipedia for Bloom filter false positives, your proposal would have a false positive probability of about 0.00726%. This assumes, among other things, that good hash functions are used. The formula is:

$(1 - (1 - [1/m])^{kn})^k$

where $m$ is the number of bits in the filter, $k$ is the number of hash functions and $n$ is the number of entries in the filter.

Because items cannot be removed from a typical Bloom filter, if generation of the filter is too expensive, you might consider a counting Bloom filter to allow deletions.

(Although I have not read of it being used and do not know if it would be effective, one might use ORed signatures in each field instead of a set bit, where each signature has half or fewer of the bits set. A possible match is found when ((entry_signature ^ test_signature) & test_signature) == 0 for each entry selected by a hash function. If every signature has the same number of set bits, this would be like nesting a Bloom filter with a size equal to the signature size and the number of hash functions equal to the number of set bits.)

Improve this answer
$\endgroup$
0
$\begingroup$

I recommend you to try Siphash, what is 64-bit, cryptographically strong and extremely fast. It's keyed so you can use as many Siphash'es as you need, each providing 64 bits of variability

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.