xor_singleheader
fastfilter_java
xor_singleheader | fastfilter_java | |
---|---|---|
2 | 1 | |
329 | 235 | |
4.0% | 0.9% | |
6.1 | 5.9 | |
2 months ago | 4 months ago | |
C | Java | |
Apache License 2.0 | Apache License 2.0 |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
xor_singleheader
- A fast alternative to the modulo reduction
-
Bloom Filters – Much, much more than a space efficient hashmap
Yes. Some variants of ribbon filters are very fast, and other variants (which are a bit slower thought) need very little space: only a few percent more than the theoretical lower bound.
For static sets, ribbon filters and binary fuse filters (e.g. here: https://github.com/FastFilter/xor_singleheader) are very competitive. Both are based on recent (2019 and newer) theoretical work from Stefan Walzer, e.g. this one https://arxiv.org/pdf/1907.04749.pdf
fastfilter_java
-
Bloom Filters – Much, much more than a space efficient hashmap
There are many alternatives to Bloom filters, but some variants of Bloom filters are still competitive. I'm one of the authors of some benchmarks for filters: https://github.com/FastFilter/fastfilter_cpp (this is based on the cuckoo filter benchmark) and https://github.com/FastFilter/fastfilter_java
For static sets (where you construct the filter once and then use it for lookup), blocked Bloom filters are the fastest, for lookup. They do need a bit more space (maybe 10% more than Bloom filters). Also very fast are binary fuse filters (which are new), and xor filters. Cuckoo filters, ribbon filters, and Bloom filters are a bit slower.
For dynamic sets (where you can add and remove entries later), the fastest (again for lookup) are probably "Succinct counting blocked Bloom filter" (no paper yet for this): they are a combination of blocked Bloom filters and counting Bloom filters, so lookup is identical to the blocked Bloom filter. Then cuckoo filters, and counting Bloom filters.
What are some alternatives?
fastfilter_cpp - Fast Approximate Membership Filters (C++)
awesome-ethereum-rollups - A list of resources related to scaling with rollups.
Golomb-coded-map - A space-efficient, associative alternative to the Bloom filter