You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@datasketches.apache.org by "hawkingrei (via GitHub)" <gi...@apache.org> on 2026/08/03 06:52:47 UTC
[PR] feat: add exact equality for Jaccard sketches (datasketches-rust)
hawkingrei opened a new pull request, #181:
URL: https://github.com/apache/datasketches-rust/pull/181
## What changed
- Add `exactly_equal` to `ThetaJaccardSimilarity` and `TupleJaccardSimilarity`.
- Reuse the key-only union path to compare retained hashes and theta.
- Keep Tuple summary values and types outside the equality comparison.
- Cover empty, mutable/compact, seed mismatch, summary-independent, and zero-retained cases.
## Why
This is a focused follow-up to #142 and its final review feedback. It adds only exact sketch-state equality; `similarity_test` and `dissimilarity_test` remain separate future work.
The zero-retained case intentionally distinguishes the two APIs: `compute` preserves an uncertain Jaccard interval, while `exactly_equal` compares the observable sketch state (retained hashes and theta), matching the other DataSketches implementations.
## Related
- Follow-up to #142
## Testing
- `cargo x prepare-testdata`
- `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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: add exact equality for Jaccard sketches (datasketches-rust)
Posted by "hawkingrei (via GitHub)" <gi...@apache.org>.
hawkingrei commented on code in PR #181:
URL: https://github.com/apache/datasketches-rust/pull/181#discussion_r3718219764
##########
datasketches/src/thetafamily/common/jaccard_similarity.rs:
##########
@@ -299,6 +269,71 @@ impl JaccardSimilarityOperator {
union.theta64(),
)
}
+
+ pub(crate) fn exactly_equal<A, B>(&self, sketch_a: &A, sketch_b: &B) -> Result<bool, Error>
+ where
+ A: ThetaKeySketchView,
+ B: ThetaKeySketchView,
+ {
+ if sketch_a.is_empty() && sketch_b.is_empty() {
+ return Ok(true);
+ }
+ if sketch_a.is_empty() || sketch_b.is_empty() {
Review Comment:
Thanks for catching this. The empty-input short-circuit is intentional, so I updated both public docs to state that seed mismatches are errors only when both sketches are non-empty. I also added Theta and Tuple regression coverage for an empty sketch paired with a non-empty sketch built with a different seed.
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: add exact equality for Jaccard sketches (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on code in PR #181:
URL: https://github.com/apache/datasketches-rust/pull/181#discussion_r3718385790
##########
datasketches/src/thetafamily/common/jaccard_similarity.rs:
##########
@@ -299,6 +269,71 @@ impl JaccardSimilarityOperator {
union.theta64(),
)
}
+
+ pub(crate) fn exactly_equal<A, B>(&self, sketch_a: &A, sketch_b: &B) -> Result<bool, Error>
+ where
+ A: ThetaKeySketchView,
+ B: ThetaKeySketchView,
+ {
+ if sketch_a.is_empty() && sketch_b.is_empty() {
+ return Ok(true);
+ }
+ if sketch_a.is_empty() || sketch_b.is_empty() {
Review Comment:
@hawkingrei @ariesdevil Is the real manner from code what other DataSketches impls do?
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: add exact equality for Jaccard sketches (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on code in PR #181:
URL: https://github.com/apache/datasketches-rust/pull/181#discussion_r3718461993
##########
datasketches/src/thetafamily/common/jaccard_similarity.rs:
##########
@@ -299,6 +269,71 @@ impl JaccardSimilarityOperator {
union.theta64(),
)
}
+
+ pub(crate) fn exactly_equal<A, B>(&self, sketch_a: &A, sketch_b: &B) -> Result<bool, Error>
+ where
+ A: ThetaKeySketchView,
+ B: ThetaKeySketchView,
+ {
+ if sketch_a.is_empty() && sketch_b.is_empty() {
+ return Ok(true);
+ }
+ if sketch_a.is_empty() || sketch_b.is_empty() {
+ return Ok(false);
+ }
+
+ let union = self.compute_union(sketch_a, sketch_b)?;
+ Ok(identical_sets(sketch_a, sketch_b, &union))
+ }
+
+ fn compute_union<A, B>(
+ &self,
+ sketch_a: &A,
+ sketch_b: &B,
+ ) -> Result<CompactSketchParts<KeyEntry>, Error>
+ where
+ A: ThetaKeySketchView,
+ B: ThetaKeySketchView,
+ {
+ self.validate_seed_hash(sketch_a)?;
+ self.validate_seed_hash(sketch_b)?;
+
+ let sketch_a = KeySketchView::new(sketch_a);
+ let sketch_b = KeySketchView::new(sketch_b);
+ let mut union = UnionState::new(
+ union_lg_k(sketch_a.num_retained(), sketch_b.num_retained()),
+ ResizeFactor::X8,
+ 1.0,
+ self.seed,
+ NoopMergePolicy,
+ );
+ union.update(&sketch_a)?;
+ union.update(&sketch_b)?;
+ Ok(union.to_compact_parts(false))
+ }
+
+ fn validate_seed_hash<S: ThetaKeySketchView>(&self, sketch: &S) -> Result<(), Error> {
+ let expected = compute_seed_hash(self.seed);
+ if expected != sketch.seed_hash() {
+ return Err(Error::invalid_argument(format!(
+ "incompatible seed hash: expected {}, got {}",
+ expected,
+ sketch.seed_hash(),
+ )));
+ }
+ Ok(())
+ }
+}
+
+fn identical_sets<A, B>(sketch_a: &A, sketch_b: &B, union: &CompactSketchParts<KeyEntry>) -> bool
Review Comment:
@ariesdevil You can use the "suggestion" feature to add a suggested comment here - https://docs.github.com/en/pull-requests/how-tos/review-pull-requests/incorporating-feedback-in-your-pull-request
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: add exact equality for Jaccard sketches (datasketches-rust)
Posted by "hawkingrei (via GitHub)" <gi...@apache.org>.
hawkingrei commented on code in PR #181:
URL: https://github.com/apache/datasketches-rust/pull/181#discussion_r3718512216
##########
datasketches/src/thetafamily/common/jaccard_similarity.rs:
##########
@@ -299,6 +269,71 @@ impl JaccardSimilarityOperator {
union.theta64(),
)
}
+
+ pub(crate) fn exactly_equal<A, B>(&self, sketch_a: &A, sketch_b: &B) -> Result<bool, Error>
+ where
+ A: ThetaKeySketchView,
+ B: ThetaKeySketchView,
+ {
+ if sketch_a.is_empty() && sketch_b.is_empty() {
+ return Ok(true);
+ }
+ if sketch_a.is_empty() || sketch_b.is_empty() {
+ return Ok(false);
+ }
+
+ let union = self.compute_union(sketch_a, sketch_b)?;
+ Ok(identical_sets(sketch_a, sketch_b, &union))
+ }
+
+ fn compute_union<A, B>(
+ &self,
+ sketch_a: &A,
+ sketch_b: &B,
+ ) -> Result<CompactSketchParts<KeyEntry>, Error>
+ where
+ A: ThetaKeySketchView,
+ B: ThetaKeySketchView,
+ {
+ self.validate_seed_hash(sketch_a)?;
+ self.validate_seed_hash(sketch_b)?;
+
+ let sketch_a = KeySketchView::new(sketch_a);
+ let sketch_b = KeySketchView::new(sketch_b);
+ let mut union = UnionState::new(
+ union_lg_k(sketch_a.num_retained(), sketch_b.num_retained()),
+ ResizeFactor::X8,
+ 1.0,
+ self.seed,
+ NoopMergePolicy,
+ );
+ union.update(&sketch_a)?;
+ union.update(&sketch_b)?;
+ Ok(union.to_compact_parts(false))
+ }
+
+ fn validate_seed_hash<S: ThetaKeySketchView>(&self, sketch: &S) -> Result<(), Error> {
+ let expected = compute_seed_hash(self.seed);
+ if expected != sketch.seed_hash() {
+ return Err(Error::invalid_argument(format!(
+ "incompatible seed hash: expected {}, got {}",
+ expected,
+ sketch.seed_hash(),
+ )));
+ }
+ Ok(())
+ }
+}
+
+fn identical_sets<A, B>(sketch_a: &A, sketch_b: &B, union: &CompactSketchParts<KeyEntry>) -> bool
Review Comment:
Thanks. I kept the C++-aligned name and added documentation in f67e857 explaining why no additional retained union keys plus matching theta values proves that both sketches have the same retained key set and theta.
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: add exact equality for Jaccard sketches (datasketches-rust)
Posted by "ariesdevil (via GitHub)" <gi...@apache.org>.
ariesdevil commented on PR #181:
URL: https://github.com/apache/datasketches-rust/pull/181#issuecomment-5176150284
rest LGTM
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: add exact equality for Jaccard sketches (datasketches-rust)
Posted by "ariesdevil (via GitHub)" <gi...@apache.org>.
ariesdevil commented on code in PR #181:
URL: https://github.com/apache/datasketches-rust/pull/181#discussion_r3710472926
##########
datasketches/src/thetafamily/common/jaccard_similarity.rs:
##########
@@ -299,6 +269,71 @@ impl JaccardSimilarityOperator {
union.theta64(),
)
}
+
+ pub(crate) fn exactly_equal<A, B>(&self, sketch_a: &A, sketch_b: &B) -> Result<bool, Error>
+ where
+ A: ThetaKeySketchView,
+ B: ThetaKeySketchView,
+ {
+ if sketch_a.is_empty() && sketch_b.is_empty() {
+ return Ok(true);
+ }
+ if sketch_a.is_empty() || sketch_b.is_empty() {
Review Comment:
`exactly_equal` returns `Ok(false)` as soon as exactly one sketch is empty, before calling `compute_union`, where seed validation happens.
But the docs in `datasketches/src/thetafamily/theta/jaccard_similarity.rs:84` and `datasketches/src/thetafamily/tuple/jaccard_similarity.rs:90` say this will return an error.
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: add exact equality for Jaccard sketches (datasketches-rust)
Posted by "ariesdevil (via GitHub)" <gi...@apache.org>.
ariesdevil commented on code in PR #181:
URL: https://github.com/apache/datasketches-rust/pull/181#discussion_r3718403949
##########
datasketches/src/thetafamily/common/jaccard_similarity.rs:
##########
@@ -299,6 +269,71 @@ impl JaccardSimilarityOperator {
union.theta64(),
)
}
+
+ pub(crate) fn exactly_equal<A, B>(&self, sketch_a: &A, sketch_b: &B) -> Result<bool, Error>
+ where
+ A: ThetaKeySketchView,
+ B: ThetaKeySketchView,
+ {
+ if sketch_a.is_empty() && sketch_b.is_empty() {
+ return Ok(true);
+ }
+ if sketch_a.is_empty() || sketch_b.is_empty() {
+ return Ok(false);
+ }
+
+ let union = self.compute_union(sketch_a, sketch_b)?;
+ Ok(identical_sets(sketch_a, sketch_b, &union))
+ }
+
+ fn compute_union<A, B>(
+ &self,
+ sketch_a: &A,
+ sketch_b: &B,
+ ) -> Result<CompactSketchParts<KeyEntry>, Error>
+ where
+ A: ThetaKeySketchView,
+ B: ThetaKeySketchView,
+ {
+ self.validate_seed_hash(sketch_a)?;
+ self.validate_seed_hash(sketch_b)?;
+
+ let sketch_a = KeySketchView::new(sketch_a);
+ let sketch_b = KeySketchView::new(sketch_b);
+ let mut union = UnionState::new(
+ union_lg_k(sketch_a.num_retained(), sketch_b.num_retained()),
+ ResizeFactor::X8,
+ 1.0,
+ self.seed,
+ NoopMergePolicy,
+ );
+ union.update(&sketch_a)?;
+ union.update(&sketch_b)?;
+ Ok(union.to_compact_parts(false))
+ }
+
+ fn validate_seed_hash<S: ThetaKeySketchView>(&self, sketch: &S) -> Result<(), Error> {
+ let expected = compute_seed_hash(self.seed);
+ if expected != sketch.seed_hash() {
+ return Err(Error::invalid_argument(format!(
+ "incompatible seed hash: expected {}, got {}",
+ expected,
+ sketch.seed_hash(),
+ )));
+ }
+ Ok(())
+ }
+}
+
+fn identical_sets<A, B>(sketch_a: &A, sketch_b: &B, union: &CompactSketchParts<KeyEntry>) -> bool
Review Comment:
Oh, I see the C++ impl uses the same name, so just adding some docs is fine for me.
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: add exact equality for Jaccard sketches (datasketches-rust)
Posted by "ariesdevil (via GitHub)" <gi...@apache.org>.
ariesdevil commented on code in PR #181:
URL: https://github.com/apache/datasketches-rust/pull/181#discussion_r3718262461
##########
datasketches/src/thetafamily/common/jaccard_similarity.rs:
##########
@@ -299,6 +269,71 @@ impl JaccardSimilarityOperator {
union.theta64(),
)
}
+
+ pub(crate) fn exactly_equal<A, B>(&self, sketch_a: &A, sketch_b: &B) -> Result<bool, Error>
+ where
+ A: ThetaKeySketchView,
+ B: ThetaKeySketchView,
+ {
+ if sketch_a.is_empty() && sketch_b.is_empty() {
+ return Ok(true);
+ }
+ if sketch_a.is_empty() || sketch_b.is_empty() {
+ return Ok(false);
+ }
+
+ let union = self.compute_union(sketch_a, sketch_b)?;
+ Ok(identical_sets(sketch_a, sketch_b, &union))
+ }
+
+ fn compute_union<A, B>(
+ &self,
+ sketch_a: &A,
+ sketch_b: &B,
+ ) -> Result<CompactSketchParts<KeyEntry>, Error>
+ where
+ A: ThetaKeySketchView,
+ B: ThetaKeySketchView,
+ {
+ self.validate_seed_hash(sketch_a)?;
+ self.validate_seed_hash(sketch_b)?;
+
+ let sketch_a = KeySketchView::new(sketch_a);
+ let sketch_b = KeySketchView::new(sketch_b);
+ let mut union = UnionState::new(
+ union_lg_k(sketch_a.num_retained(), sketch_b.num_retained()),
+ ResizeFactor::X8,
+ 1.0,
+ self.seed,
+ NoopMergePolicy,
+ );
+ union.update(&sketch_a)?;
+ union.update(&sketch_b)?;
+ Ok(union.to_compact_parts(false))
+ }
+
+ fn validate_seed_hash<S: ThetaKeySketchView>(&self, sketch: &S) -> Result<(), Error> {
+ let expected = compute_seed_hash(self.seed);
+ if expected != sketch.seed_hash() {
+ return Err(Error::invalid_argument(format!(
+ "incompatible seed hash: expected {}, got {}",
+ expected,
+ sketch.seed_hash(),
+ )));
+ }
+ Ok(())
+ }
+}
+
+fn identical_sets<A, B>(sketch_a: &A, sketch_b: &B, union: &CompactSketchParts<KeyEntry>) -> bool
Review Comment:
This function name is a little bit confuse, add some docs or renaming to `same_retained_keys_and_theta` seems better.
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: add exact equality for Jaccard sketches (datasketches-rust)
Posted by "ariesdevil (via GitHub)" <gi...@apache.org>.
ariesdevil commented on code in PR #181:
URL: https://github.com/apache/datasketches-rust/pull/181#discussion_r3718400122
##########
datasketches/src/thetafamily/common/jaccard_similarity.rs:
##########
@@ -299,6 +269,71 @@ impl JaccardSimilarityOperator {
union.theta64(),
)
}
+
+ pub(crate) fn exactly_equal<A, B>(&self, sketch_a: &A, sketch_b: &B) -> Result<bool, Error>
+ where
+ A: ThetaKeySketchView,
+ B: ThetaKeySketchView,
+ {
+ if sketch_a.is_empty() && sketch_b.is_empty() {
+ return Ok(true);
+ }
+ if sketch_a.is_empty() || sketch_b.is_empty() {
Review Comment:
yup, https://github.com/apache/datasketches-cpp/blob/c22888581964fc490feee835766cc8c3adb722e0/theta/include/theta_jaccard_similarity_base.hpp#L85
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: add exact equality for Jaccard sketches (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun merged PR #181:
URL: https://github.com/apache/datasketches-rust/pull/181
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org