Timeline for Bloom filter implementation using a BitArray
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 23, 2014 at 0:32 | vote | accept | aarti | ||
| Oct 22, 2014 at 21:47 | history | edited | Flambino | CC BY-SA 3.0 |
added 82 characters in body
|
| Oct 22, 2014 at 15:45 | history | edited | Flambino | CC BY-SA 3.0 |
deleted 22 characters in body
|
| Oct 22, 2014 at 14:35 | history | edited | Flambino | CC BY-SA 3.0 |
added 7 characters in body
|
| Oct 22, 2014 at 14:26 | comment | added | Flambino | @gitarchie I've added a big chunk at the end of my answer, which you might find interesting. It was just something I did for fun, but this is absolutely not my area of expertise, so take it with a grain of salt :) | |
| Oct 22, 2014 at 14:18 | history | edited | Flambino | CC BY-SA 3.0 |
large addendum
|
| Oct 22, 2014 at 4:53 | comment | added | aarti | oh ok, I don't know the answer to that, But Google's bloom filter selects optimal parameters based on expected false positive rate. I don't understand all of it, it is in cpp, Maybe you will code.google.com/p/bloom | |
| Oct 21, 2014 at 21:55 | comment | added | Flambino | @gitarchie Perhaps my understanding is flawed, but that question pertains reusing hashing functions (w/ seeding); not the output of said hashing function. My point is that if the hash of an item sets fewer than k bits, then you increase the risk of false positives. If e.g. k is 5, but the item hash you're using only sets a single bit, then the question of whether the filter includes the item hinges one just 1 bit - not five. Thus, the false positive rate will increase. The rate will be somewhere between the rate for k = 1 and k = 5 | |
| Oct 21, 2014 at 21:44 | comment | added | aarti | Why do you think digest is flawed, I asked a question here and implemented based on answer and reference implementation I found. programmers.stackexchange.com/questions/260459/… | |
| Oct 21, 2014 at 21:23 | comment | added | Flambino |
@gitarchie Whoops - sorry about missing the comments at the top. Must've scrolled around, and not scrolled all the way back. As for using #hash, yours is a fair point. At least with a single hashing method, it's easy to swap out the logic there (especially since it's flawed)
|
|
| Oct 21, 2014 at 21:21 | history | edited | Flambino | CC BY-SA 3.0 |
typos/edit
|
| Oct 21, 2014 at 21:19 | comment | added | aarti |
I DID consider using ruby's Hash but since it seeds a new value for each process I decided that would not be good. Other implementations I have seen use CRC32. Hashes use the division method to fit into an array so that is what I used. I have the documentation for those variables at the top. I added link to another implementation that I was using to understand the functionality.
|
|
| Oct 21, 2014 at 21:00 | history | answered | Flambino | CC BY-SA 3.0 |