freakyzoidberg opened a new pull request, #740: URL: https://github.com/apache/datasketches-java/pull/740
## Summary Adds an immutable **Xor Filter** for probabilistic set membership to a new `org.apache.datasketches.filters.xorfilter` package, as a smaller/faster alternative to the existing Bloom filter. The API, naming, Javadoc, exception handling, serialization layout, and `MemorySegment` support mirror `BloomFilter`. Implements the algorithm from Graf & Lemire, *"Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters,"* ACM JEA 2020, with 8-bit and 16-bit fingerprints. ## What's included - `XorFilter` — immutable filter: peeling construction, 3-hash membership query, the full typed `query(...)` suite (`long`/`double`/`String`/`byte[]`/`char[]`/ `short[]`/`int[]`/`long[]`/`MemorySegment`), `heapify`/`wrap`, `toByteArray`/`toLongArray`, and a BloomFilter-style `toString`. - `XorFilterBuilder` — accumulates items via a matching typed `update(...)` suite, de-duplicates, and builds; plus static `create(long[]...)` factories. - `package-info.java`, `XorFilterTest` (24 tests), and a standalone `XorFilterBenchmark`. - `Family`: new `XORFILTER(22, "XORFILTER", 3, 3)` entry. ## Design notes - Items are reduced to 64-bit keys once (xxHash64), then mapped to positions and a fingerprint via a MurmurHash3 finalizer keyed on a construction seed that is re-drawn (splitmix64) if a rare 2-core remains, capped at 100 attempts. - Fingerprint array capacity is `floor(1.23*n) + 32`, rounded down to a multiple of 3. - Serialization uses a fixed 3-long preamble (the filter has no empty/growable state) followed by the raw fingerprint bytes; layout is documented in an ASCII table in `XorFilter`. ## Testing - 24 new unit tests + existing filters/`Family` tests pass on JDK 25 (no false negatives; typed items; duplicates; empty; determinism; heapify/wrap/toLongArray round-trips for 8- and 16-bit; corruption guards). - `apache-rat` license check passes (0 unapproved). - Benchmark confirms the paper's expectations: bits/item = 9.84 (8-bit) / 19.68 (16-bit); observed FPP ~= 1/256 and ~= 1/65536. ## Follow-ups (not in this PR) - Cross-language (C++/Go) serialization compatibility test, a la `BloomFilterCrossLanguageTest`. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
