3 ms·

As u/nyc640 said, it is actually the other way around. False positives are possible. False negatives are not. The original paper linked gives the false positive

by pkd 9y ago

As u/nyc640 said, it is actually the other way around. False positives are possible. False negatives are not. The original paper linked gives the false positive rates of upto 0.19% (0.09% for the semi-sorted version).

onli 9y ago
Okay. Thanks. I read the readme that this is more for academic purposes, and saw nyc640 explanation (thanks as well!). But when reading the Readme I wondered "How would this go together with something like https://github.com/SamSaffron/lru_redux https://github.com/SamSaffron/lru_redux ?" Do you have thoughts on that? I use both the lru_redux as well as https://github.com/jnicklas/memoit https://github.com/jnicklas/memoit in a ruby app of mine, and if another gem (like a memoization scheme using a Cuckoo Filter) would improve performance it would be fun to try it out. But it is of course possible that this is not applicable, or it would just not be faster. I think it should not be an advantage (given that the others will be at its core just a hash map, so you don't need that membership test), but that's why I asked.
- pkd 9y ago
  I can't really tell you if the Cuckoo Filter will improve performance since it depends on so many factors. But if you have some free time then why not try it out and find out for yourself? In case you do, please let me know what performance you derive out of it :) I wrote it is mainly for academic purposes because the main advantage of Cuckoo Filter is that it takes a lot less space than other similar filters. It achieves that by using only a certain amount of bits(6) to store the fingerprint etc. In Ruby, you can't really control memory allocation on a bit/byte level so you lose that advantage. The rest mainly remains the same. I suspect the bottleneck in this implementation is the hashing algorithm (FNV-1a). I chose it because of its relatively good collision resistance. Plugging in a faster hash algorithm would definitely improve performance.

by pkd 9y ago

onli 9y ago

Okay. Thanks. I read the readme that this is more for academic purposes, and saw nyc640 explanation (thanks as well!). But when reading the Readme I wondered "How would this go together with something like https://github.com/SamSaffron/lru_redux https://github.com/SamSaffron/lru_redux ?" Do you have thoughts on that? I use both the lru_redux as well as https://github.com/jnicklas/memoit https://github.com/jnicklas/memoit in a ruby app of mine, and if another gem (like a memoization scheme using a Cuckoo Filter) would improve performance it would be fun to try it out. But it is of course possible that this is not applicable, or it would just not be faster. I think it should not be an advantage (given that the others will be at its core just a hash map, so you don't need that membership test), but that's why I asked.

pkd 9y ago
I can't really tell you if the Cuckoo Filter will improve performance since it depends on so many factors. But if you have some free time then why not try it out and find out for yourself? In case you do, please let me know what performance you derive out of it :) I wrote it is mainly for academic purposes because the main advantage of Cuckoo Filter is that it takes a lot less space than other similar filters. It achieves that by using only a certain amount of bits(6) to store the fingerprint etc. In Ruby, you can't really control memory allocation on a bit/byte level so you lose that advantage. The rest mainly remains the same. I suspect the bottleneck in this implementation is the hashing algorithm (FNV-1a). I chose it because of its relatively good collision resistance. Plugging in a faster hash algorithm would definitely improve performance.