tisonkun opened a new pull request, #278:
URL: https://github.com/apache/datasketches-rust/pull/278
Supersedes #271 and closes #270.
## Summary
Remove `BloomFilter::invert` and add `BloomFilter::difference`, a bitwise
AND-NOT set difference — the transformation other DataSketches libraries expose
as A NOT B.
## Why remove `invert`
Bit inversion is a leaked bit-array primitive without a sound set-membership
interpretation of its own:
- As an absence oracle ("`true` means definitely not inserted"), an inverted
filter is strictly worse than the original filter, whose `false` answers
already mean "definitely not inserted" with a much higher hit rate (`1 - FPP`
versus `(1 - load)^k`).
- Other boolean compositions involving inversion have no per-item set
meaning: NOR (`!(A | B)`) is already answered exactly by a union's `false`, and
NAND has no clean set-level reading.
- Updates after inversion assert "definitely absent" facts whose soundness
precondition the filter cannot check, and the semantically correct update
(recording a new insertion into the original stream) would require clearing
bits — the deletion a Bloom filter cannot support.
- Neither Guava nor Spark, which the Java implementation was compared
against, exposes inversion; it exists only as boolean-completeness of the
internal bit-array abstraction, and nothing in the Java, C++, or PostgreSQL
codebases uses it outside a smoke test.
The only composition with a clean per-item meaning is `A AND NOT B`, so
expose it directly instead of the raw primitive.
## `difference` semantics
After `left.difference(&right)`:
- Items inserted into `right` always return `false`: they are excluded
exactly.
- Items inserted only into `left` keep returning `true` unless one of their
hash positions is occupied in `right`. Unlike `union()` and `intersect()`, this
operation can drop items, with a probability that grows with `right`'s load
factor. This is inherent to any materialized Bloom-filter subtraction and is
documented on the method.
- Items never inserted into `left` may still return `true` (false
positives), at a rate no higher than before the operation.
The method requires compatible filters (same capacity, hash count, and
seed), matching `union()` and `intersect()`. The serialized format is
unchanged, so cross-language compatibility is unaffected.
## Changes
- `datasketches/src/bloom/sketch.rs`: replace `invert()` with
`difference()`; document the exact-exclusion and item-drop semantics; remove
the now-unneeded post-invert qualifications from the type and `is_empty()`
documentation.
- `datasketches/src/bloom/mod.rs`: update the guarantee summary and the
set-operations example.
- `tests-integration/tests/bloom_test/sketch.rs`: replace the invert
round-trip test with difference tests covering exact exclusion of right items,
disjoint-item retention, self-difference clearing, empty-right identity,
incompatible-filter rejection, and bit-count consistency across serialization.
- `CHANGELOG.md`: breaking-change entry with migration, new-feature entry.
## Validation
- `cargo x check`
- `cargo x test`
- `cargo x lint`
--
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]
