jaideeppyne opened a new pull request, #246:
URL: https://github.com/apache/datasketches-rust/pull/246
`ThetaJaccardSimilarity::compute` and `TupleJaccardSimilarity::compute`
return `{0.0, 0.5, 1.0}` instead of `1.0` when both inputs are non-empty, share
a theta, and retain no entries. You get that state from a low sampling
probability. So a sketch is not similar to itself:
```rust
let mut s =
ThetaSketchBuilder::default().sampling_probability(1e-12).build()?;
s.update("apple");
assert!(!s.is_empty());
assert_eq!(s.num_retained(), 0);
ThetaJaccardSimilarity::default().compute(&s, &s)?; // {0.0, 0.5, 1.0}, want
1.0
```
`exactly_equal` already returns `true` for that same pair, so the two
operators contradict each other today.
The cause is the extra `!union.entries.is_empty() &&` guard in front of the
shared `identical_sets` check. When both inputs retain nothing the union
retains nothing, the guard skips the identity shortcut, and it falls through to
the ratio bounds with a union count of zero. C++ has no such guard in
`jaccard_similarity_base::jaccard`. Dropping it is the whole fix.
I checked what C++ 5.2.0 actually returns before touching anything:
| inputs (both non-empty, 0 retained) | C++ | Rust before | Rust after |
| --- | --- | --- | --- |
| equal theta | `{1, 1, 1}` | `{0, 0.5, 1}` | `{1, 1, 1}` |
| different theta | `{0, 0.5, 1}` | `{0, 0.5, 1}` | `{0, 0.5, 1}` |
The C++ side was two separately deserialized objects, not the same object
twice, so this is not the `&sketch_a == &sketch_b` shortcut.
That means the existing
`test_distinct_non_empty_sketches_with_no_retained_entries_are_uncertain` in
both the theta and tuple suites asserted the wrong value. Its two sketches both
used `sampling_probability(1e-12)`, so they had equal theta and were not
actually distinct, and the test also asserted `exactly_equal == true` right
below the `0.5` estimate. I split it: the equal-theta pair now asserts `1.0`,
and a new test keeps the uncertain `{0, 0.5, 1}` branch using the genuinely
different theta (`1e-12` vs `2e-12`), which is the case C++ agrees is
uncertain. Third test covers a sketch against itself.
### How I found it
`pip install datasketches` gives the C++ core through Python. I ran the same
operation in both engines over identical serialized inputs and diffed the
numbers, rather than comparing serialized results.
1700 randomized theta cases (random `lg_k` per input and per union, `n` from
0 to 40k, overlapping and disjoint key ranges, sampling probability in `{1,
0.5, 0.1, 1e-9, 1e-12}`), comparing `num_retained`, `theta64`, `estimate`,
`is_empty`, `is_estimation_mode`, lower and upper bounds at 1/2/3 std dev for
each of A, B, union, intersection, A-not-B, plus the Jaccard triple and
`exactly_equal`. 654 of those cases hit the non-empty-with-zero-retained state.
Everything else in theta matched exactly; the Jaccard triple was the only
divergence, and it is 0 after this change.
I ran the same harness over CPC (250 cases, unions across mismatched `lg_k`,
all flavors) and T-Digest (250 cases, mismatched `k`, merges in both orders and
8-deep merge chains) and found no divergence, so this PR is only about Jaccard.
Both new tests fail on `c8b20c8` with the test change alone and pass with
the source change. `cargo x test` and `cargo x lint` are clean.
Claude Code wrote the harness and the patch under my review.
--
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]
