This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
The following commit(s) were added to refs/heads/main by this push:
new f33bca5 fix(theta,tuple): treat equal-theta sketches with no retained
entries as identical (#246)
f33bca5 is described below
commit f33bca53787a41a6c4ac2461298d6613f11a2a94
Author: Jaideep Pyne <[email protected]>
AuthorDate: Sun Aug 30 22:39:42 2026 +0530
fix(theta,tuple): treat equal-theta sketches with no retained entries as
identical (#246)
Co-authored-by: jaideeppyne <[email protected]>
Co-authored-by: Claude Opus 4.8 <[email protected]>
---
CHANGELOG.md | 1 +
.../src/thetafamily/common/jaccard_similarity.rs | 2 +-
.../tests/theta_test/jaccard_similarity.rs | 56 +++++++++++++---------
.../tests/tuple_test/jaccard_similarity.rs | 52 +++++++++++++-------
4 files changed, 70 insertions(+), 41 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 7e1c725..aaf8efd 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -43,6 +43,7 @@ All significant changes to this project will be documented in
this file.
* Compact HLL4 images now restore all register values correctly.
* `HllSketch::lower_bound` now uses the number of non-zero registers as a
floor in HLL mode, matching Java, C++, and Go and avoiding a bound below the
distinct count already proven by register hits.
* `HllUnion` now keeps a single HLL-mode input's estimate stable when copying
or downsampling it and keeps confidence bounds consistent across HLL4, HLL6,
and HLL8 result types, matching Java and C++.
+* `ThetaJaccardSimilarity` and `TupleJaccardSimilarity` now report an exact
similarity of `1.0` for two non-empty sketches that share a theta and retain no
entries, matching Java and C++ and agreeing with `exactly_equal` on the same
pair. Such pairs, which arise from a low sampling probability, previously
returned the uncertain `{0.0, 0.5, 1.0}` interval, so a sketch was not similar
to itself.
* HLL, Theta, and Tuple deserializers now return `InvalidData` for malformed
payload sizes and entry counts instead of risking oversized allocations or
decoding failures.
* Malformed CPC images now return `InvalidData` instead of panicking.
* Seeded deserializers now return `InvalidData` rather than panicking when the
caller supplies a seed whose hash is the reserved zero value.
diff --git a/datasketches/src/thetafamily/common/jaccard_similarity.rs
b/datasketches/src/thetafamily/common/jaccard_similarity.rs
index 7d47323..a761cbd 100644
--- a/datasketches/src/thetafamily/common/jaccard_similarity.rs
+++ b/datasketches/src/thetafamily/common/jaccard_similarity.rs
@@ -187,7 +187,7 @@ where
let sketch_a_state = (a_num_retained, a_theta);
let sketch_b_state = (b_num_retained, b_theta);
let union = compute_union(seed, sketch_a, sketch_b)?;
- if !union.entries.is_empty() && identical_sets(sketch_a_state,
sketch_b_state, &union) {
+ if identical_sets(sketch_a_state, sketch_b_state, &union) {
return Ok(JaccardSimilarity::exact(1.0));
}
diff --git a/tests-integration/tests/theta_test/jaccard_similarity.rs
b/tests-integration/tests/theta_test/jaccard_similarity.rs
index 2a44b67..be29b75 100644
--- a/tests-integration/tests/theta_test/jaccard_similarity.rs
+++ b/tests-integration/tests/theta_test/jaccard_similarity.rs
@@ -56,6 +56,21 @@ fn sketch_with_range_and_seed(start: u64, count: u64, seed:
u64) -> ThetaSketch
sketch
}
+fn non_empty_sketch_without_retained_entries(
+ sampling_probability: f32,
+ value: &str,
+) -> ThetaSketch {
+ let mut sketch = ThetaSketchBuilder::default()
+ .sampling_probability(sampling_probability)
+ .build()
+ .unwrap();
+ sketch.update(value);
+
+ assert!(!sketch.is_empty());
+ assert_eq!(sketch.num_retained(), 0);
+ sketch
+}
+
#[test]
fn test_empty() {
let sketch_a = ThetaSketchBuilder::default().build().unwrap();
@@ -184,35 +199,30 @@ fn test_seed_mismatch() {
}
#[test]
-fn test_distinct_non_empty_sketches_with_no_retained_entries_are_uncertain() {
- let mut sketch_a = ThetaSketchBuilder::default()
- .sampling_probability(1e-12)
- .build()
- .unwrap();
- let mut sketch_b = ThetaSketchBuilder::default()
- .sampling_probability(1e-12)
- .build()
- .unwrap();
- let mut different_theta = ThetaSketchBuilder::default()
- .sampling_probability(2e-12)
- .build()
- .unwrap();
- sketch_a.update("apple");
- sketch_b.update("banana");
- different_theta.update("orange");
+fn
test_equal_theta_non_empty_sketches_with_no_retained_entries_are_identical() {
+ let sketch_a = non_empty_sketch_without_retained_entries(1e-12, "apple");
+ let sketch_b = non_empty_sketch_without_retained_entries(1e-12, "banana");
- assert!(!sketch_a.is_empty());
- assert!(!sketch_b.is_empty());
- assert_eq!(sketch_a.num_retained(), 0);
- assert_eq!(sketch_b.num_retained(), 0);
- assert_eq!(different_theta.num_retained(), 0);
+ assert_eq!(sketch_a.theta64(), sketch_b.theta64());
let operator = ThetaJaccardSimilarity::default();
- let jaccard = operator.compute(&sketch_a, &sketch_b).unwrap();
+ assert_jaccard_exact(operator.compute(&sketch_a, &sketch_b).unwrap(), 1.0);
+ assert_jaccard_exact(operator.compute(&sketch_a, &sketch_a).unwrap(), 1.0);
+ assert!(operator.exactly_equal(&sketch_a, &sketch_b).unwrap());
+}
+
+#[test]
+fn
test_distinct_theta_non_empty_sketches_with_no_retained_entries_are_uncertain()
{
+ let sketch_a = non_empty_sketch_without_retained_entries(1e-12, "apple");
+ let different_theta = non_empty_sketch_without_retained_entries(2e-12,
"orange");
+
+ assert_ne!(sketch_a.theta64(), different_theta.theta64());
+
+ let operator = ThetaJaccardSimilarity::default();
+ let jaccard = operator.compute(&sketch_a, &different_theta).unwrap();
assert_eq!(jaccard.lower_bound(), 0.0);
assert_eq!(jaccard.estimate(), 0.5);
assert_eq!(jaccard.upper_bound(), 1.0);
- assert!(operator.exactly_equal(&sketch_a, &sketch_b).unwrap());
assert!(!operator.exactly_equal(&sketch_a, &different_theta).unwrap());
}
diff --git a/tests-integration/tests/tuple_test/jaccard_similarity.rs
b/tests-integration/tests/tuple_test/jaccard_similarity.rs
index bbe2e6c..3d4b6f5 100644
--- a/tests-integration/tests/tuple_test/jaccard_similarity.rs
+++ b/tests-integration/tests/tuple_test/jaccard_similarity.rs
@@ -18,6 +18,7 @@
use datasketches::thetacommon::JaccardSimilarity;
use datasketches::tuple::DefaultUpdatePolicy;
use datasketches::tuple::TupleJaccardSimilarity;
+use datasketches::tuple::TupleSketch;
use datasketches::tuple::TupleSketchBuilder;
use googletest::assert_that;
use googletest::prelude::anything;
@@ -43,6 +44,21 @@ fn assert_jaccard_estimate(actual: JaccardSimilarity,
expected: f64) {
assert_close(actual.upper_bound(), expected, 0.01);
}
+fn non_empty_sketch_without_retained_entries(
+ sampling_probability: f32,
+ value: &str,
+) -> TupleSketch<DefaultUpdatePolicy<u64>> {
+ let mut sketch = default_tuple_sketch_builder()
+ .sampling_probability(sampling_probability)
+ .build()
+ .unwrap();
+ sketch.update(value, 1u64);
+
+ assert!(!sketch.is_empty());
+ assert_eq!(sketch.num_retained(), 0);
+ sketch
+}
+
#[test]
fn test_empty() {
let sketch_a = default_tuple_sketch_builder().build().unwrap();
@@ -134,28 +150,30 @@ fn test_custom_seed_and_seed_mismatch() {
}
#[test]
-fn test_distinct_non_empty_sketches_with_no_retained_entries_are_uncertain() {
- let mut sketch_a = default_tuple_sketch_builder()
- .sampling_probability(1e-12)
- .build()
- .unwrap();
- let mut sketch_b = default_tuple_sketch_builder()
- .sampling_probability(1e-12)
- .build()
- .unwrap();
- sketch_a.update("apple", 1u64);
- sketch_b.update("banana", 1u64);
+fn
test_equal_theta_non_empty_sketches_with_no_retained_entries_are_identical() {
+ let sketch_a = non_empty_sketch_without_retained_entries(1e-12, "apple");
+ let sketch_b = non_empty_sketch_without_retained_entries(1e-12, "banana");
- assert!(!sketch_a.is_empty());
- assert!(!sketch_b.is_empty());
- assert_eq!(sketch_a.num_retained(), 0);
- assert_eq!(sketch_b.num_retained(), 0);
+ assert_eq!(sketch_a.theta64(), sketch_b.theta64());
let operator = TupleJaccardSimilarity::default();
- let jaccard = operator.compute(&sketch_a, &sketch_b).unwrap();
+ assert_jaccard_exact(operator.compute(&sketch_a, &sketch_b).unwrap(), 1.0);
+ assert_jaccard_exact(operator.compute(&sketch_a, &sketch_a).unwrap(), 1.0);
+ assert!(operator.exactly_equal(&sketch_a, &sketch_b).unwrap());
+}
+
+#[test]
+fn
test_distinct_theta_non_empty_sketches_with_no_retained_entries_are_uncertain()
{
+ let sketch_a = non_empty_sketch_without_retained_entries(1e-12, "apple");
+ let different_theta = non_empty_sketch_without_retained_entries(2e-12,
"orange");
+
+ assert_ne!(sketch_a.theta64(), different_theta.theta64());
+
+ let operator = TupleJaccardSimilarity::default();
+ let jaccard = operator.compute(&sketch_a, &different_theta).unwrap();
assert_eq!(jaccard.lower_bound(), 0.0);
assert_eq!(jaccard.estimate(), 0.5);
assert_eq!(jaccard.upper_bound(), 1.0);
- assert!(operator.exactly_equal(&sketch_a, &sketch_b).unwrap());
+ assert!(!operator.exactly_equal(&sketch_a, &different_theta).unwrap());
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
