34 lines
1.1 KiB
Markdown
34 lines
1.1 KiB
Markdown
# bloom filters
|
|
|
|
> This is an educational implementation for bloom filters and is meant to be low LOC
|
|
|
|
- The api is inspired a bit from the [Guava impl](https://github.com/google/guava/blob/master/guava/src/com/google/common/hash/BloomFilter.java#L99)
|
|
- For hashes it uses xxhash - the specific implementations shared [here](https://create.stephan-brumme.com/xxhash/#sourcecode)
|
|
|
|
Other than that the overall implementation itself is very short owing to the fact that this
|
|
works on byte chunks directly instead of understanding specific types ( and hence having handling
|
|
for it which some libraries do )
|
|
|
|
Correctness I've verified via plots.
|
|
|
|
### Plots
|
|
|
|
|
|
|
|
|
|
|
|
To regenerate:
|
|
|
|
```sh
|
|
cmake --build build
|
|
./build/bloom_filter_stats_csv plots/data/cases.csv > plots/data/bloom_filter_stats.csv
|
|
gnuplot plots/gnuplot/fpp_vs_k.gp
|
|
gnuplot plots/gnuplot/fpp_vs_n.gp
|
|
gnuplot plots/gnuplot/fpp_vs_m.gp
|
|
```
|
|
|
|
# Todo
|
|
|
|
- perf benchmarks
|
|
- modern variations added
|