XOR_singleheader: Header-only binary fuse and XOR filter library
9 months ago
- #data-structures
- #filtering
- #performance
- Bloom filters are used to quickly check set membership, but xor filters and binary fuse filters are faster and more concise alternatives.
- Binary fuse filters and xor filters are naturally compressible and smaller than cuckoo filters.
- The library is header-only, implements both binary fuse and xor filters, and is available under the Apache license.
- Basic usage involves allocating, populating, and querying the filter with functions like `binary_fuse8_allocate`, `binary_fuse8_populate`, and `binary_fuse8_contain`.
- There are 8-bit and 16-bit versions, with the 16-bit version offering lower false-positive probability at the cost of more memory.
- Serialization options include unpacked (faster) and packed (smaller but slower) formats.
- Construction of binary fuse filters requires temporary memory (~24 bytes per entry), but can be done with minimal temporary memory at a slower speed.
- The library includes testing and benchmarking tools to evaluate performance and correctness.
- Bug reports and fixes are encouraged, but the project does not aim to be warning-free under all static analyzers.