MaxFreedomPollard opened a new pull request, #778:
URL: https://github.com/apache/datasketches-java/pull/778
`org.apache.datasketches.theta.JaccardSimilarity.exactlyEqual(a, b)` throws
when the two sketches are small:
```java
UpdatableThetaSketch a = UpdatableThetaSketch.builder().build();
UpdatableThetaSketch b = UpdatableThetaSketch.builder().build();
a.update(1);
b.update(1);
JaccardSimilarity.exactlyEqual(a, b);
// SketchesArgumentException: Nominal Entries must be >= 16 and <= 67108864:
2
```
On the same pair, `jaccard(a, b)` returns `[1.0, 1.0, 1.0]` and the tuple
`JaccardSimilarity.exactlyEqual` returns `true`.
### Root cause
`exactlyEqual()` sizes its union with `ceilingPowerOf2(countA + countB)` and
passes that straight to `ThetaSetOperationBuilder.setNominalEntries()`, which
only accepts 16 to 2^26 (`JaccardSimilarity.java:120`). So any two non-empty
sketches whose retained counts add up to 8 or less make it throw. That includes
p-sampled sketches that are non-empty but retain no entries: the count is 0, so
the requested size is 1. A total above 2^26 throws too.
This is #153 again. That issue reported the same expression in `jaccard()`.
The 2017 fix (e22e016d) clamped the size there to `[1 << MIN_LG_NOM_LONGS, 1 <<
MAX_LG_NOM_LONGS]` and left `exactlyEqual()` unchanged. In C++, `jaccard()` and
`exactly_equal()` share one clamped `compute_union()`
(`theta/include/theta_jaccard_similarity_base.hpp`).
### Fix
This copies the three clamping lines from `jaccard()` into `exactlyEqual()`.
With the clamp, the result is exact for sketches configured with up to 2^25
nominal entries, because two equal sketches of that size never retain more than
2^26 entries, so the union keeps all of them. Two equal sketches that each
retain more than 2^26 entries (which needs 2^26 nominal entries) now return
false instead of throwing, because the union result is cut back to 2^26
entries. A javadoc note says so, modelled on the one `jaccard()` already has.
| pair | main | this PR |
|---|---|---|
| 1 item vs the same item | throws | true |
| 1 item vs a different item | throws | false |
| 4 items vs the same 4 items | throws | true |
| compact copies of the 1-item sketches | throws | true |
| both non-empty, p = 0.0001, no retained entries | throws | true |
| 5 items vs the same 5 items | true | true |
The new `JaccardSimilarityTest.checkMinKExactlyEqual` follows `checkMinK`,
which was added for `jaccard()` with #153.
### Verification
Maven Central was not reachable from my environment, so I could not run `mvn
test`, and the TestNG suite has not been run on this change. What I did
instead, with Temurin 25.0.4.1 on macOS aarch64:
- Compiled all of `src/main/java` with `javac --release 25 -Xlint:all
-Xdoclint:all/protected`. There were no diagnostics for this class.
- Compiled the theta and tuple `JaccardSimilarityTest` classes against a
minimal local stand-in for `org.testng.annotations.Test` and
`org.testng.Assert`, then called every `@Test` method by reflection.
- On main, the new test fails with the exception above and the other 7
theta tests pass.
- With the fix, all 8 theta tests and all 13 tuple tests pass.
- Ran a small harness for the cases in the table, against main and against
the fix.
I did not run the case above 2^26. It needs several GB of heap, so that part
is reasoned from the code only.
🤖 Generated with [Claude Code](https://claude.com/claude-code)
--
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]
