tisonkun opened a new issue, #766: URL: https://github.com/apache/datasketches-java/issues/766
## Summary `BloomFilter.invert()` flips the backing bit array, but the resulting object has no sound set-membership interpretation of its own, and nothing in the DataSketches ecosystem appears to use it. The only boolean composition involving inversion that has a clean per-item meaning is `A AND NOT B`. We suggest deprecating or removing `invert()` and, if the use case is wanted, exposing an explicit A NOT B (set difference) operation with documented semantics. The C++ implementation mirrors this API and the same considerations apply there. This came up while reviewing the equivalent Rust API; the Rust implementation now removes `invert()` in favor of `BloomFilter::difference`: https://github.com/apache/datasketches-rust/pull/278 (see also https://github.com/apache/datasketches-rust/issues/194 for the contract problems around `invert`). ## What an inverted filter actually means Let `B` be the bit array before inversion and `S(x)` the `k` hash positions of an item `x`: - `query(x) == true` after inversion means every position of `S(x)` was `0` in `B`, so `x` was **definitely not** inserted before the inversion. This direction is certain. - `query(x) == false` means at least one position was `1` in `B`. All inserted items land here, but so does any absent item with at least one colliding position — with probability roughly `1 - (1 - load)^k`, close to 1 for typical configurations. So `false` carries little information. - Inversion is not the exact logical complement of the pre-inversion answer: `true` requires *all* `k` positions to have been clear, not merely one. Consequences: 1. **As an absence oracle, an inverted filter is strictly worse than the original.** A normal filter's `false` already means "definitely not inserted", with hit rate `1 - FPP`; the inverted filter's certain `true` answers fire with probability only `(1 - load)^k`. 2. **Updates after inversion have no checkable set-level meaning.** `update()` after inversion only sets bits, manufacturing new "definitely absent" claims that are sound only if the item was absent before inversion — a precondition the filter cannot verify. The semantically correct opposite update (recording a new insertion into the original stream) would require *clearing* bits, the deletion a Bloom filter cannot support. 3. **Other compositions involving inversion are meaningless or redundant.** NOR (`!(A | B)`) is already answered exactly by a union's `false`; NAND has no per-item set-level reading. ## The one meaningful composition: A AND NOT B `R = A AND (NOT B)` does have a clean interpretation, which is presumably what `invert()` was meant to enable: - Items inserted into `B` always query `false` in `R`: they are excluded exactly. - Items inserted only into `A` are retained unless one of their hash positions is occupied in `B` — so unlike union and intersection, a materialized difference **can drop items**, with probability growing in `B`'s load factor. (Note this is *not* pointwise-equivalent to `queryA(x) && !queryB(x)`: the materialized form requires all of `x`'s positions to be clear in `B`, which is stronger.) - False positives for items never inserted into `A` remain bounded by `A`'s false positive rate. This is a legitimate distributed-systems building block (materialize "A minus B" as a single serializable, composable artifact). But users need the difference operation, not an exposed inverted intermediate state. An `andNot(BloomFilter other)` on `BloomFilter` (or on `BitArray`) with the semantics above documented would serve that use case directly; the wire format needs no change. ## Evidence that `invert()` is unused and poorly understood - The original Bloom filter PR (#513) discusses Guava and Spark as reference points, but neither Guava's nor Spark's `BloomFilter` exposes inversion; the PR discussion never mentions `invert()`, and the `BitArray.invert()` method carries no javadoc. It appears to exist for boolean-completeness of the internal bit-array abstraction (AND/OR/NOT) rather than for an articulated use case. - A search of datasketches-java, datasketches-cpp, and datasketches-postgresql finds no usage outside the implementations' own smoke tests. - The C++ smoke test itself (`filters/test/bloom_filter_test.cpp`) asserts that after `invert()`, "original items should be mostly not-present" (`num_found < n / 10`). Inserted items are in fact **always** not-present after inversion (all their positions are `0`), so `num_found` is deterministically zero — suggesting the operation's semantics are fuzzy even to its maintainers. ## Proposal 1. Deprecate `BloomFilter.invert()` (and `BitArray.invert()` if it is public surface) with a pointer to the semantics above. 2. Optionally add an A NOT B operation (`andNot`) with documented exact-exclusion and item-drop semantics, consistent with how the Theta family exposes A NOT B across languages. 3. Align with C++ (same API, same considerations) and Rust (already removing `invert()` in favor of `difference`) so the three implementations converge. -- 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]
