Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
4  
Hard to say as you haven't told us your goals etc, making this open ended. You best bet is to experiment. –  Aryabhata Sep 19 '12 at 17:58
    
@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. –  Aadith Sep 19 '12 at 19:05
    
Can you go deeper into the specifics? Like what is actually the criterion? –  Aryabhata Sep 20 '12 at 3:10
    
Criterion - the URL should have appeared in web search results in the past 7 days at least 5 times –  Aadith Sep 20 '12 at 9:54
    
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. –  Aryabhata Sep 20 '12 at 15:21
add comment

2 Answers 2

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.)

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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