hesela.devXOR filter
An XOR filter is a static approximate-membership structure whose lookup compares a key fingerprint with the XOR of shared array entries.
Construction uses the complete key set; singleton peeling and reverse assignment establish member equations. A failed peel requires another construction attempt, not a negative membership answer. [1] The no-false-negative property assumes a successful, unchanged representation and consistent queries.
Relations
- related
- binary-fuse-filter, bloom-filter, ribbon-filter, sstable
Citations
- Graf and Lemire. Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters. ACM JEA 25 (2020). DOI: 10.1145/3376122.
- Hesela. Static filters and reproducible fixed-equation examples.
Sources & caveats
- The linked fixed-equation example is synthetic and does not estimate collision rates. [2]