This is an automated email from the ASF dual-hosted git repository. leerho pushed a commit to branch jaccard-seed-and-tuple-clamp in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit d02f5156b1497ba72e2e1af681b5efb3a5117d70 Author: Lee Rhodes <[email protected]> AuthorDate: Wed Oct 28 14:35:54 2026 -0700 Align theta and tuple JaccardSimilarity, and check theta seeds in tuple set operations Theta JaccardSimilarity: - Add seed overloads of jaccard, exactlyEqual, similarityTest and dissimilarityTest, as in C++ and Go. Sketches created with a custom seed previously could not be compared at all. Tuple JaccardSimilarity: - Share the union and identical-sets code through private helpers, as theta does, replacing four copies. - Clamp the union size in exactlyEqual to the legal range of nominal entries, as tuple jaccard, theta, C++ and Go already do. - Return early when jaccard is given the same sketch twice. Tuple set operations: - TupleUnion, TupleIntersection and TupleAnotB now reject a non-empty ThetaSketch created with a non-default seed. Tuple sketches always use the default seed, so such input previously gave silently wrong results. - ThetaSketch.getSeedHash() is now public, as get_seed_hash() is in C++. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- .../datasketches/theta/DirectCompactSketch.java | 2 +- .../theta/DirectQuickSelectSketchR.java | 2 +- .../datasketches/theta/EmptyCompactSketch.java | 2 +- .../datasketches/theta/HeapCompactSketch.java | 2 +- .../datasketches/theta/HeapUpdateSketch.java | 2 +- .../datasketches/theta/JaccardSimilarity.java | 87 ++++++++++- .../datasketches/theta/SingleItemSketch.java | 2 +- .../org/apache/datasketches/theta/ThetaSketch.java | 6 +- .../datasketches/theta/WrappedCompactSketch.java | 2 +- .../datasketches/tuple/JaccardSimilarity.java | 164 +++++++++++---------- .../org/apache/datasketches/tuple/TupleAnotB.java | 2 + .../datasketches/tuple/TupleIntersection.java | 1 + .../org/apache/datasketches/tuple/TupleUnion.java | 1 + .../java/org/apache/datasketches/tuple/Util.java | 16 ++ .../datasketches/theta/JaccardSimilarityTest.java | 28 ++++ .../datasketches/tuple/JaccardSimilarityTest.java | 36 +++++ .../datasketches/tuple/ThetaSeedHashTest.java | 88 +++++++++++ 17 files changed, 349 insertions(+), 94 deletions(-) diff --git a/src/main/java/org/apache/datasketches/theta/DirectCompactSketch.java b/src/main/java/org/apache/datasketches/theta/DirectCompactSketch.java index 749d8dfed..6c01d78a9 100644 --- a/src/main/java/org/apache/datasketches/theta/DirectCompactSketch.java +++ b/src/main/java/org/apache/datasketches/theta/DirectCompactSketch.java @@ -173,7 +173,7 @@ class DirectCompactSketch extends CompactThetaSketch { } @Override - short getSeedHash() { + public short getSeedHash() { return (short) extractSeedHash(seg_); } } diff --git a/src/main/java/org/apache/datasketches/theta/DirectQuickSelectSketchR.java b/src/main/java/org/apache/datasketches/theta/DirectQuickSelectSketchR.java index 37fabf844..8a68c34a9 100644 --- a/src/main/java/org/apache/datasketches/theta/DirectQuickSelectSketchR.java +++ b/src/main/java/org/apache/datasketches/theta/DirectQuickSelectSketchR.java @@ -247,7 +247,7 @@ class DirectQuickSelectSketchR extends UpdatableThetaSketch { } @Override - short getSeedHash() { + public short getSeedHash() { return (short) PreambleUtil.extractSeedHash(wseg_); } diff --git a/src/main/java/org/apache/datasketches/theta/EmptyCompactSketch.java b/src/main/java/org/apache/datasketches/theta/EmptyCompactSketch.java index 27dc1de75..f381b6b0b 100644 --- a/src/main/java/org/apache/datasketches/theta/EmptyCompactSketch.java +++ b/src/main/java/org/apache/datasketches/theta/EmptyCompactSketch.java @@ -161,7 +161,7 @@ final class EmptyCompactSketch extends CompactThetaSketch { } @Override - short getSeedHash() { + public short getSeedHash() { return 0; } diff --git a/src/main/java/org/apache/datasketches/theta/HeapCompactSketch.java b/src/main/java/org/apache/datasketches/theta/HeapCompactSketch.java index 2e0fed42f..dd25f85b7 100644 --- a/src/main/java/org/apache/datasketches/theta/HeapCompactSketch.java +++ b/src/main/java/org/apache/datasketches/theta/HeapCompactSketch.java @@ -130,7 +130,7 @@ final class HeapCompactSketch extends CompactThetaSketch { } @Override - short getSeedHash() { + public short getSeedHash() { return seedHash_; } diff --git a/src/main/java/org/apache/datasketches/theta/HeapUpdateSketch.java b/src/main/java/org/apache/datasketches/theta/HeapUpdateSketch.java index e676a6652..79284e362 100644 --- a/src/main/java/org/apache/datasketches/theta/HeapUpdateSketch.java +++ b/src/main/java/org/apache/datasketches/theta/HeapUpdateSketch.java @@ -88,7 +88,7 @@ abstract class HeapUpdateSketch extends UpdatableThetaSketch { //restricted methods @Override - short getSeedHash() { + public short getSeedHash() { return Util.computeSeedHash(getSeed()); } diff --git a/src/main/java/org/apache/datasketches/theta/JaccardSimilarity.java b/src/main/java/org/apache/datasketches/theta/JaccardSimilarity.java index f35b246fb..7aa41cb8d 100644 --- a/src/main/java/org/apache/datasketches/theta/JaccardSimilarity.java +++ b/src/main/java/org/apache/datasketches/theta/JaccardSimilarity.java @@ -21,6 +21,7 @@ package org.apache.datasketches.theta; import static java.lang.Math.max; import static java.lang.Math.min; +import static org.apache.datasketches.common.Util.DEFAULT_UPDATE_SEED; import static org.apache.datasketches.common.Util.ceilingPowerOf2; import static org.apache.datasketches.thetacommon.BoundsOnRatiosInThetaSketchedSets.getEstimateOfBoverA; import static org.apache.datasketches.thetacommon.BoundsOnRatiosInThetaSketchedSets.getLowerBoundForBoverA; @@ -49,23 +50,41 @@ public final class JaccardSimilarity { * <p>Note: For very large pairs of sketches, where the configured nominal entries of the sketches * are 2^25 or 2^26, this method may produce unpredictable results. * + * <p>Both sketches must have been created with the default update seed.</p> + * * @param sketchA given sketch A * @param sketchB given sketch B * @return a double array {LowerBound, Estimate, UpperBound} of the Jaccard index. * The Upper and Lower bounds are for a confidence interval of 95.4% or +/- 2 standard deviations. */ public static double[] jaccard(final ThetaSketch sketchA, final ThetaSketch sketchB) { + return jaccard(sketchA, sketchB, DEFAULT_UPDATE_SEED); + } + + /** + * Computes the Jaccard similarity index with upper and lower bounds, for two sketches created + * with the given update seed. See {@link #jaccard(ThetaSketch, ThetaSketch)}. + * + * @param sketchA given sketch A + * @param sketchB given sketch B + * @param seed the update seed that both sketches were created with. + * <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a> + * @return a double array {LowerBound, Estimate, UpperBound} of the Jaccard index. + * The Upper and Lower bounds are for a confidence interval of 95.4% or +/- 2 standard deviations. + */ + public static double[] jaccard(final ThetaSketch sketchA, final ThetaSketch sketchB, + final long seed) { //Corner case checks if (sketchA == null || sketchB == null) { return ZEROS.clone(); } if (sketchA == sketchB) { return ONES.clone(); } if (sketchA.isEmpty() && sketchB.isEmpty()) { return ONES.clone(); } if (sketchA.isEmpty() || sketchB.isEmpty()) { return ZEROS.clone(); } - final ThetaSketch unionAB = computeUnion(sketchA, sketchB); + final ThetaSketch unionAB = computeUnion(sketchA, sketchB, seed); if (identicalSets(sketchA, sketchB, unionAB)) { return ONES.clone(); } //Create the ThetaIntersection - final ThetaIntersection inter = ThetaSetOperation.builder().buildIntersection(); + final ThetaIntersection inter = ThetaSetOperation.builder().setSeed(seed).buildIntersection(); inter.intersect(sketchA); inter.intersect(sketchB); inter.intersect(unionAB); //ensures that intersection is a subset of the union @@ -84,19 +103,37 @@ public final class JaccardSimilarity { * <p>Note: For very large pairs of sketches, where the configured nominal entries of the sketches * are 2^26, this method may return false even if the two sketches are equal. * + * <p>Both sketches must have been created with the default update seed.</p> + * * @param sketchA the given sketch A * @param sketchB the given sketch B * @return true if the two given sketches have exactly the same hash values and the same * theta values. */ public static boolean exactlyEqual(final ThetaSketch sketchA, final ThetaSketch sketchB) { + return exactlyEqual(sketchA, sketchB, DEFAULT_UPDATE_SEED); + } + + /** + * Returns true if the two given sketches, created with the given update seed, have exactly the + * same hash values and the same theta values. See {@link #exactlyEqual(ThetaSketch, ThetaSketch)}. + * + * @param sketchA the given sketch A + * @param sketchB the given sketch B + * @param seed the update seed that both sketches were created with. + * <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a> + * @return true if the two given sketches have exactly the same hash values and the same + * theta values. + */ + public static boolean exactlyEqual(final ThetaSketch sketchA, final ThetaSketch sketchB, + final long seed) { //Corner case checks if (sketchA == null || sketchB == null) { return false; } if (sketchA == sketchB) { return true; } if (sketchA.isEmpty() && sketchB.isEmpty()) { return true; } if (sketchA.isEmpty() || sketchB.isEmpty()) { return false; } - final ThetaSketch unionAB = computeUnion(sketchA, sketchB); + final ThetaSketch unionAB = computeUnion(sketchA, sketchB, seed); return identicalSets(sketchA, sketchB, unionAB); } @@ -115,10 +152,27 @@ public final class JaccardSimilarity { */ public static boolean similarityTest(final ThetaSketch measured, final ThetaSketch expected, final double threshold) { + return similarityTest(measured, expected, threshold, DEFAULT_UPDATE_SEED); + } + + /** + * Tests similarity of a measured ThetaSketch against an expected ThetaSketch, both created + * with the given update seed. See {@link #similarityTest(ThetaSketch, ThetaSketch, double)}. + * + * @param measured the sketch to be tested + * @param expected the reference sketch that is considered to be correct. + * @param threshold a real value between zero and one. + * @param seed the update seed that both sketches were created with. + * <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a> + * @return if true, the similarity of the two sketches is greater than the given threshold + * with at least 97.7% confidence. + */ + public static boolean similarityTest(final ThetaSketch measured, final ThetaSketch expected, + final double threshold, final long seed) { //index 0: the lower bound //index 1: the mean estimate //index 2: the upper bound - final double jRatioLB = jaccard(measured, expected)[0]; //choosing the lower bound + final double jRatioLB = jaccard(measured, expected, seed)[0]; //choosing the lower bound return jRatioLB >= threshold; } @@ -137,10 +191,27 @@ public final class JaccardSimilarity { */ public static boolean dissimilarityTest(final ThetaSketch measured, final ThetaSketch expected, final double threshold) { + return dissimilarityTest(measured, expected, threshold, DEFAULT_UPDATE_SEED); + } + + /** + * Tests dissimilarity of a measured ThetaSketch against an expected ThetaSketch, both created + * with the given update seed. See {@link #dissimilarityTest(ThetaSketch, ThetaSketch, double)}. + * + * @param measured the sketch to be tested + * @param expected the reference sketch that is considered to be correct. + * @param threshold a real value between zero and one. + * @param seed the update seed that both sketches were created with. + * <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a> + * @return if true, the dissimilarity of the two sketches is greater than the given threshold + * with at least 97.7% confidence. + */ + public static boolean dissimilarityTest(final ThetaSketch measured, final ThetaSketch expected, + final double threshold, final long seed) { //index 0: the lower bound //index 1: the mean estimate //index 2: the upper bound - final double jRatioUB = jaccard(measured, expected)[2]; //choosing the upper bound + final double jRatioUB = jaccard(measured, expected, seed)[2]; //choosing the upper bound return jRatioUB <= threshold; } @@ -150,16 +221,18 @@ public final class JaccardSimilarity { * because only its retained entries and theta are used. * @param sketchA the given sketch A * @param sketchB the given sketch B + * @param seed the update seed that both sketches were created with * @return the unordered union of sketch A and sketch B */ - private static ThetaSketch computeUnion(final ThetaSketch sketchA, final ThetaSketch sketchB) { + private static ThetaSketch computeUnion(final ThetaSketch sketchA, final ThetaSketch sketchB, + final long seed) { final int countA = sketchA.getRetainedEntries(true); final int countB = sketchB.getRetainedEntries(true); final int minK = 1 << ThetaUtil.MIN_LG_NOM_LONGS; final int maxK = 1 << ThetaUtil.MAX_LG_NOM_LONGS; final int newK = max(min(ceilingPowerOf2(countA + countB), maxK), minK); final ThetaUnion union = - ThetaSetOperation.builder().setNominalEntries(newK).buildUnion(); + ThetaSetOperation.builder().setNominalEntries(newK).setSeed(seed).buildUnion(); union.union(sketchA); union.union(sketchB); return union.getResult(false, null); diff --git a/src/main/java/org/apache/datasketches/theta/SingleItemSketch.java b/src/main/java/org/apache/datasketches/theta/SingleItemSketch.java index 57112fedd..64c064f52 100644 --- a/src/main/java/org/apache/datasketches/theta/SingleItemSketch.java +++ b/src/main/java/org/apache/datasketches/theta/SingleItemSketch.java @@ -380,7 +380,7 @@ final class SingleItemSketch extends CompactThetaSketch { } @Override - short getSeedHash() { + public short getSeedHash() { return (short) (pre0_ >>> 48); } diff --git a/src/main/java/org/apache/datasketches/theta/ThetaSketch.java b/src/main/java/org/apache/datasketches/theta/ThetaSketch.java index 8dcefacdc..48062e8d9 100644 --- a/src/main/java/org/apache/datasketches/theta/ThetaSketch.java +++ b/src/main/java/org/apache/datasketches/theta/ThetaSketch.java @@ -584,10 +584,12 @@ public abstract class ThetaSketch implements MemorySegmentStatus { MemorySegment getMemorySegment() { return null; } /** - * Gets the 16-bit seed hash + * Gets the 16-bit hash of the update seed that this sketch was created with. Set operations use it + * to check that their inputs were created with the same seed. + * <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a> * @return the seed hash */ - abstract short getSeedHash(); + public abstract short getSeedHash(); static boolean getEmpty(final MemorySegment srcSeg) { checkSegPreambleCap(srcSeg); diff --git a/src/main/java/org/apache/datasketches/theta/WrappedCompactSketch.java b/src/main/java/org/apache/datasketches/theta/WrappedCompactSketch.java index 2a33a386a..53ef5c176 100644 --- a/src/main/java/org/apache/datasketches/theta/WrappedCompactSketch.java +++ b/src/main/java/org/apache/datasketches/theta/WrappedCompactSketch.java @@ -139,7 +139,7 @@ class WrappedCompactSketch extends CompactThetaSketch { } @Override - short getSeedHash() { + public short getSeedHash() { return getShortLE(bytes_, SEED_HASH_SHORT); } } diff --git a/src/main/java/org/apache/datasketches/tuple/JaccardSimilarity.java b/src/main/java/org/apache/datasketches/tuple/JaccardSimilarity.java index bc0c1e5b3..421df0131 100644 --- a/src/main/java/org/apache/datasketches/tuple/JaccardSimilarity.java +++ b/src/main/java/org/apache/datasketches/tuple/JaccardSimilarity.java @@ -71,29 +71,13 @@ public final class JaccardSimilarity { final SummarySetOperations<S> summarySetOps) { //Corner case checks if (sketchA == null || sketchB == null) { return ZEROS.clone(); } + if (sketchA == sketchB) { return ONES.clone(); } if (sketchA.isEmpty() && sketchB.isEmpty()) { return ONES.clone(); } if (sketchA.isEmpty() || sketchB.isEmpty()) { return ZEROS.clone(); } - final int countA = sketchA.getRetainedEntries(); - final int countB = sketchB.getRetainedEntries(); - - //Create the TupleUnion - final int minK = 1 << ThetaUtil.MIN_LG_NOM_LONGS; - final int maxK = 1 << ThetaUtil.MAX_LG_NOM_LONGS; - final int newK = max(min(ceilingPowerOf2(countA + countB), maxK), minK); - final TupleUnion<S> union = new TupleUnion<>(newK, summarySetOps); - union.union(sketchA); - union.union(sketchB); - - final TupleSketch<S> unionAB = union.getResult(); - final long thetaLongUAB = unionAB.getThetaLong(); - final long thetaLongA = sketchA.getThetaLong(); - final long thetaLongB = sketchB.getThetaLong(); - final int countUAB = unionAB.getRetainedEntries(); - - //Check for identical data - if (countUAB == countA && countUAB == countB - && thetaLongUAB == thetaLongA && thetaLongUAB == thetaLongB) { + final TupleSketch<S> unionAB = computeUnion(sketchA, sketchB, summarySetOps); + if (identicalSets(sketchA.getRetainedEntries(), sketchA.getThetaLong(), + sketchB.getRetainedEntries(), sketchB.getThetaLong(), unionAB)) { return ONES.clone(); } @@ -142,26 +126,9 @@ public final class JaccardSimilarity { if (sketchA.isEmpty() && sketchB.isEmpty()) { return ONES.clone(); } if (sketchA.isEmpty() || sketchB.isEmpty()) { return ZEROS.clone(); } - final int countA = sketchA.getRetainedEntries(); - final int countB = sketchB.getRetainedEntries(true); - - //Create the Tuple/Theta Union - final int minK = 1 << ThetaUtil.MIN_LG_NOM_LONGS; - final int maxK = 1 << ThetaUtil.MAX_LG_NOM_LONGS; - final int newK = max(min(ceilingPowerOf2(countA + countB), maxK), minK); - final TupleUnion<S> union = new TupleUnion<>(newK, summarySetOps); - union.union(sketchA); - union.union(sketchB, summary); - - final TupleSketch<S> unionAB = union.getResult(); - final long thetaLongUAB = unionAB.getThetaLong(); - final long thetaLongA = sketchA.getThetaLong(); - final long thetaLongB = sketchB.getThetaLong(); - final int countUAB = unionAB.getRetainedEntries(); - - //Check for identical data - if (countUAB == countA && countUAB == countB - && thetaLongUAB == thetaLongA && thetaLongUAB == thetaLongB) { + final TupleSketch<S> unionAB = computeUnion(sketchA, sketchB, summary, summarySetOps); + if (identicalSets(sketchA.getRetainedEntries(), sketchA.getThetaLong(), + sketchB.getRetainedEntries(true), sketchB.getThetaLong(), unionAB)) { return ONES.clone(); } @@ -198,25 +165,9 @@ public final class JaccardSimilarity { if (sketchA.isEmpty() && sketchB.isEmpty()) { return true; } if (sketchA.isEmpty() || sketchB.isEmpty()) { return false; } - final int countA = sketchA.getRetainedEntries(); - final int countB = sketchB.getRetainedEntries(); - - //Create the TupleUnion - final TupleUnion<S> union = new TupleUnion<>(ceilingPowerOf2(countA + countB), summarySetOps); - union.union(sketchA); - union.union(sketchB); - final TupleSketch<S> unionAB = union.getResult(); - final long thetaLongUAB = unionAB.getThetaLong(); - final long thetaLongA = sketchA.getThetaLong(); - final long thetaLongB = sketchB.getThetaLong(); - final int countUAB = unionAB.getRetainedEntries(); - - //Check for identical counts and thetas - if (countUAB == countA && countUAB == countB - && thetaLongUAB == thetaLongA && thetaLongUAB == thetaLongB) { - return true; - } - return false; + final TupleSketch<S> unionAB = computeUnion(sketchA, sketchB, summarySetOps); + return identicalSets(sketchA.getRetainedEntries(), sketchA.getThetaLong(), + sketchB.getRetainedEntries(), sketchB.getThetaLong(), unionAB); } /** @@ -244,25 +195,9 @@ public final class JaccardSimilarity { if (sketchA.isEmpty() && sketchB.isEmpty()) { return true; } if (sketchA.isEmpty() || sketchB.isEmpty()) { return false; } - final int countA = sketchA.getRetainedEntries(); - final int countB = sketchB.getRetainedEntries(true); - - //Create the TupleUnion - final TupleUnion<S> union = new TupleUnion<>(ceilingPowerOf2(countA + countB), summarySetOps); - union.union(sketchA); - union.union(sketchB, summary); - final TupleSketch<S> unionAB = union.getResult(); - final long thetaLongUAB = unionAB.getThetaLong(); - final long thetaLongA = sketchA.getThetaLong(); - final long thetaLongB = sketchB.getThetaLong(); - final int countUAB = unionAB.getRetainedEntries(); - - //Check for identical counts and thetas - if (countUAB == countA && countUAB == countB - && thetaLongUAB == thetaLongA && thetaLongUAB == thetaLongB) { - return true; - } - return false; + final TupleSketch<S> unionAB = computeUnion(sketchA, sketchB, summary, summarySetOps); + return identicalSets(sketchA.getRetainedEntries(), sketchA.getThetaLong(), + sketchB.getRetainedEntries(true), sketchB.getThetaLong(), unionAB); } /** @@ -373,4 +308,77 @@ public final class JaccardSimilarity { return jRatioUB <= threshold; } + /** + * Computes the union of the two given TupleSketches. See {@link #newUnion(int, SummarySetOperations)}. + * @param sketchA the given TupleSketch A + * @param sketchB the given TupleSketch B + * @param summarySetOps instance of SummarySetOperations used to unify summaries. + * @param <S> Summary + * @return the unordered union of sketch A and sketch B + */ + private static <S extends Summary> TupleSketch<S> computeUnion( + final TupleSketch<S> sketchA, + final TupleSketch<S> sketchB, + final SummarySetOperations<S> summarySetOps) { + final TupleUnion<S> union = + newUnion(sketchA.getRetainedEntries() + sketchB.getRetainedEntries(), summarySetOps); + union.union(sketchA); + union.union(sketchB); + return union.getResult(); + } + + /** + * Computes the union of the given TupleSketch and ThetaSketch. See {@link #newUnion(int, SummarySetOperations)}. + * @param sketchA the given TupleSketch A + * @param sketchB the given ThetaSketch B + * @param summary the given proxy summary for the ThetaSketch. + * @param summarySetOps instance of SummarySetOperations used to unify summaries. + * @param <S> Summary + * @return the unordered union of sketch A and sketch B + */ + private static <S extends Summary> TupleSketch<S> computeUnion( + final TupleSketch<S> sketchA, + final ThetaSketch sketchB, + final S summary, final SummarySetOperations<S> summarySetOps) { + final TupleUnion<S> union = + newUnion(sketchA.getRetainedEntries() + sketchB.getRetainedEntries(true), summarySetOps); + union.union(sketchA); + union.union(sketchB, summary); + return union.getResult(); + } + + /** + * Creates a TupleUnion sized to hold the given total number of retained entries, clamped to the + * legal range of nominal entries. + * @param totalCount the sum of the retained entries of the two sketches + * @param summarySetOps instance of SummarySetOperations used to unify summaries. + * @param <S> Summary + * @return a new TupleUnion + */ + private static <S extends Summary> TupleUnion<S> newUnion( + final int totalCount, final SummarySetOperations<S> summarySetOps) { + final int minK = 1 << ThetaUtil.MIN_LG_NOM_LONGS; + final int maxK = 1 << ThetaUtil.MAX_LG_NOM_LONGS; + final int newK = max(min(ceilingPowerOf2(totalCount), maxK), minK); + return new TupleUnion<>(newK, summarySetOps); + } + + /** + * Returns true if the two given sketches and their union all have the same number of retained + * entries and the same theta, which means the two sketches hold identical sets. + * @param countA the retained entries of sketch A + * @param thetaLongA the theta of sketch A + * @param countB the retained entries of sketch B + * @param thetaLongB the theta of sketch B + * @param unionAB the union of sketch A and sketch B + * @return true if the two given sketches hold identical sets + */ + private static boolean identicalSets(final int countA, final long thetaLongA, + final int countB, final long thetaLongB, final TupleSketch<?> unionAB) { + final int countUAB = unionAB.getRetainedEntries(); + final long thetaLongUAB = unionAB.getThetaLong(); + return countUAB == countA && countUAB == countB + && thetaLongUAB == thetaLongA && thetaLongUAB == thetaLongB; + } + } diff --git a/src/main/java/org/apache/datasketches/tuple/TupleAnotB.java b/src/main/java/org/apache/datasketches/tuple/TupleAnotB.java index cdc6f18cf..e10a27a47 100644 --- a/src/main/java/org/apache/datasketches/tuple/TupleAnotB.java +++ b/src/main/java/org/apache/datasketches/tuple/TupleAnotB.java @@ -222,6 +222,7 @@ public final class TupleAnotB<S extends Summary> { */ public void notB(final ThetaSketch skB) { if (skB == null) { return; } //ignore + Util.checkThetaSeedHash(skB); final long thetaLongB = skB.getThetaLong(); final int countB = skB.getRetainedEntries(); @@ -417,6 +418,7 @@ public final class TupleAnotB<S extends Summary> { if (skA == null || skB == null) { throw new SketchesArgumentException("Neither argument may be null for this stateless operation."); } + Util.checkThetaSeedHash(skB); final long thetaLongA = skA.getThetaLong(); final int countA = skA.getRetainedEntries(); diff --git a/src/main/java/org/apache/datasketches/tuple/TupleIntersection.java b/src/main/java/org/apache/datasketches/tuple/TupleIntersection.java index 0ddbbf294..3eb0a54d9 100644 --- a/src/main/java/org/apache/datasketches/tuple/TupleIntersection.java +++ b/src/main/java/org/apache/datasketches/tuple/TupleIntersection.java @@ -150,6 +150,7 @@ public class TupleIntersection<S extends Summary> { public void intersect(final ThetaSketch thetaSketch, final S summary) { if (thetaSketch == null) { throw new SketchesArgumentException("ThetaSketch must not be null"); } if (summary == null) { throw new SketchesArgumentException("Summary cannot be null."); } + Util.checkThetaSeedHash(thetaSketch); final boolean firstCall = firstCall_; firstCall_ = false; // input sketch is not null, could be first or next call diff --git a/src/main/java/org/apache/datasketches/tuple/TupleUnion.java b/src/main/java/org/apache/datasketches/tuple/TupleUnion.java index d624c017a..c052a6414 100644 --- a/src/main/java/org/apache/datasketches/tuple/TupleUnion.java +++ b/src/main/java/org/apache/datasketches/tuple/TupleUnion.java @@ -126,6 +126,7 @@ public class TupleUnion<S extends Summary> { if (summary == null) { throw new SketchesArgumentException("Summary cannot be null."); } if (thetaSketch == null || thetaSketch.isEmpty()) { return; } + Util.checkThetaSeedHash(thetaSketch); empty_ = false; final long thetaIn = thetaSketch.getThetaLong(); unionThetaLong_ = min(thetaIn, unionThetaLong_); diff --git a/src/main/java/org/apache/datasketches/tuple/Util.java b/src/main/java/org/apache/datasketches/tuple/Util.java index 45168fa4a..a50490320 100644 --- a/src/main/java/org/apache/datasketches/tuple/Util.java +++ b/src/main/java/org/apache/datasketches/tuple/Util.java @@ -20,12 +20,16 @@ package org.apache.datasketches.tuple; import static java.nio.charset.StandardCharsets.UTF_8; +import static org.apache.datasketches.common.Util.DEFAULT_UPDATE_SEED; import static org.apache.datasketches.common.Util.ceilingPowerOf2; +import static org.apache.datasketches.common.Util.checkSeedHashes; +import static org.apache.datasketches.common.Util.computeSeedHash; import static org.apache.datasketches.hash.XxHash.hashCharArr; import static org.apache.datasketches.hash.XxHash.hashString; import java.lang.reflect.Array; +import org.apache.datasketches.theta.ThetaSketch; import org.apache.datasketches.thetacommon.ThetaUtil; /** @@ -33,12 +37,24 @@ import org.apache.datasketches.thetacommon.ThetaUtil; */ public final class Util { private static final int PRIME = 0x7A3C_CA71; + private static final short DEFAULT_SEED_HASH = computeSeedHash(DEFAULT_UPDATE_SEED); /** * No argument constructor. */ public Util() { } + /** + * Checks that the given ThetaSketch was created with the default update seed, which is the seed + * that all TupleSketches use. Null and empty sketches are not checked. + * @param thetaSketch the given ThetaSketch + * @throws org.apache.datasketches.common.SketchesArgumentException if the seed hashes do not match + */ + static void checkThetaSeedHash(final ThetaSketch thetaSketch) { + if (thetaSketch == null || thetaSketch.isEmpty()) { return; } + checkSeedHashes(DEFAULT_SEED_HASH, thetaSketch.getSeedHash()); + } + /** * Converts a <i>double</i> to a <i>long[]</i>. * @param value the given double value diff --git a/src/test/java/org/apache/datasketches/theta/JaccardSimilarityTest.java b/src/test/java/org/apache/datasketches/theta/JaccardSimilarityTest.java index 17cadcc92..93272e704 100644 --- a/src/test/java/org/apache/datasketches/theta/JaccardSimilarityTest.java +++ b/src/test/java/org/apache/datasketches/theta/JaccardSimilarityTest.java @@ -19,11 +19,16 @@ package org.apache.datasketches.theta; +import static org.apache.datasketches.theta.JaccardSimilarity.dissimilarityTest; import static org.apache.datasketches.theta.JaccardSimilarity.exactlyEqual; import static org.apache.datasketches.theta.JaccardSimilarity.jaccard; +import static org.apache.datasketches.theta.JaccardSimilarity.similarityTest; +import static org.testng.Assert.assertEquals; import static org.testng.Assert.assertFalse; import static org.testng.Assert.assertTrue; +import static org.testng.Assert.fail; +import org.apache.datasketches.common.SketchesArgumentException; import org.testng.annotations.Test; /** @@ -244,6 +249,29 @@ public class JaccardSimilarityTest { assertFalse(exactlyEqual(skA, skB)); } + @Test + public void checkCustomSeed() { + final long seed = 123L; + final UpdatableThetaSketch skA = UpdatableThetaSketch.builder().setSeed(seed).build(); + final UpdatableThetaSketch skB = UpdatableThetaSketch.builder().setSeed(seed).build(); + for (int i = 0; i < 1000; i++) { skA.update(i); skB.update(i); } + assertTrue(exactlyEqual(skA, skB, seed)); + assertEquals(jaccard(skA, skB, seed), new double[] {1.0, 1.0, 1.0}); + assertTrue(similarityTest(skA, skB, 0.95, seed)); + assertFalse(dissimilarityTest(skA, skB, 0.95, seed)); + + for (int i = 1000; i < 2000; i++) { skB.update(i); } + assertFalse(exactlyEqual(skA, skB, seed)); + final double[] result = jaccard(skA, skB, seed); + assertEquals(result[1], 0.5, 0.0); + assertFalse(similarityTest(skA, skB, 0.95, seed)); + assertTrue(dissimilarityTest(skA, skB, 0.95, seed)); + + //the default-seed methods reject sketches made with another seed + try { exactlyEqual(skA, skB); fail(); } catch (final SketchesArgumentException e) { } + try { jaccard(skA, skB); fail(); } catch (final SketchesArgumentException e) { } + } + @Test public void printlnTest() { println("PRINTING: "+this.getClass().getName()); diff --git a/src/test/java/org/apache/datasketches/tuple/JaccardSimilarityTest.java b/src/test/java/org/apache/datasketches/tuple/JaccardSimilarityTest.java index d21623e77..8c3739488 100644 --- a/src/test/java/org/apache/datasketches/tuple/JaccardSimilarityTest.java +++ b/src/test/java/org/apache/datasketches/tuple/JaccardSimilarityTest.java @@ -25,7 +25,9 @@ import static org.apache.datasketches.tuple.JaccardSimilarity.jaccard; import static org.apache.datasketches.tuple.JaccardSimilarity.similarityTest; import static org.testng.Assert.assertFalse; import static org.testng.Assert.assertTrue; +import static org.testng.Assert.fail; +import org.apache.datasketches.common.SketchesArgumentException; import org.apache.datasketches.theta.UpdatableThetaSketch; import org.apache.datasketches.theta.UpdatableThetaSketchBuilder; import org.apache.datasketches.tuple.adouble.DoubleSummary; @@ -442,6 +444,40 @@ public class JaccardSimilarityTest { println(result[0] + ", " + result[1] + ", " + result[2]); } + @Test + public void checkMinKExactlyEqual1() { // tuple, tuple + final UpdatableTupleSketch<Double, DoubleSummary> skA = tupleBldr.build(); //4096 + final UpdatableTupleSketch<Double, DoubleSummary> skB = tupleBldr.build(); //4096 + skA.update(1, constSummary); + skB.update(1, constSummary); + assertTrue(exactlyEqual(skA, skB, dsso)); + skB.update(2, constSummary); + assertFalse(exactlyEqual(skA, skB, dsso)); + } + + @Test + public void checkMinKExactlyEqual2() { // tuple, theta + final UpdatableTupleSketch<Double, DoubleSummary> skA = tupleBldr.build(); //4096 + final UpdatableThetaSketch skB = UpdatableThetaSketch.builder().build(); //4096 + skA.update(1, constSummary); + skB.update(1); + assertTrue(exactlyEqual(skA, skB, factory.newSummary(), dsso)); + skB.update(2); + assertFalse(exactlyEqual(skA, skB, factory.newSummary(), dsso)); + } + + @Test + public void checkThetaWithCustomSeedRejected() { + final UpdatableTupleSketch<Double, DoubleSummary> skA = tupleBldr.build(); + final UpdatableThetaSketch skB = UpdatableThetaSketch.builder().setSeed(123L).build(); + skA.update(1, constSummary); + skB.update(1); + try { jaccard(skA, skB, factory.newSummary(), dsso); fail(); } + catch (final SketchesArgumentException e) { } + try { exactlyEqual(skA, skB, factory.newSummary(), dsso); fail(); } + catch (final SketchesArgumentException e) { } + } + @Test public void printlnTest() { println("PRINTING: "+this.getClass().getName()); diff --git a/src/test/java/org/apache/datasketches/tuple/ThetaSeedHashTest.java b/src/test/java/org/apache/datasketches/tuple/ThetaSeedHashTest.java new file mode 100644 index 000000000..956079f07 --- /dev/null +++ b/src/test/java/org/apache/datasketches/tuple/ThetaSeedHashTest.java @@ -0,0 +1,88 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.datasketches.tuple; + +import static org.testng.Assert.assertEquals; +import static org.testng.Assert.fail; + +import org.apache.datasketches.common.SketchesArgumentException; +import org.apache.datasketches.theta.UpdatableThetaSketch; +import org.apache.datasketches.tuple.adouble.DoubleSummary; +import org.apache.datasketches.tuple.adouble.DoubleSummaryFactory; +import org.apache.datasketches.tuple.adouble.DoubleSummarySetOperations; +import org.testng.annotations.Test; + +/** + * Checks that the TupleSketch set operations reject a ThetaSketch created with a non-default seed. + */ +public class ThetaSeedHashTest { + private final DoubleSummary.Mode umode = DoubleSummary.Mode.Sum; + private final DoubleSummarySetOperations dsso = new DoubleSummarySetOperations(); + private final DoubleSummaryFactory factory = new DoubleSummaryFactory(umode); + + private UpdatableTupleSketch<Double, DoubleSummary> tupleSketch() { + final UpdatableTupleSketch<Double, DoubleSummary> sk = + new UpdatableTupleSketchBuilder<>(factory).build(); + for (int i = 0; i < 10; i++) { sk.update(i, 1.0); } + return sk; + } + + private static UpdatableThetaSketch thetaSketch(final long seed, final int n) { + final UpdatableThetaSketch sk = UpdatableThetaSketch.builder().setSeed(seed).build(); + for (int i = 0; i < n; i++) { sk.update(i); } + return sk; + } + + @Test + public void checkUnion() { + final TupleUnion<DoubleSummary> union = new TupleUnion<>(dsso); + try { union.union(thetaSketch(123L, 10), factory.newSummary()); fail(); } + catch (final SketchesArgumentException e) { } + union.union(thetaSketch(123L, 0), factory.newSummary()); //empty is ignored + union.union(thetaSketch(9001L, 10), factory.newSummary()); //default seed + assertEquals(union.getResult().getRetainedEntries(), 10); + } + + @Test + public void checkIntersection() { + final TupleIntersection<DoubleSummary> inter = new TupleIntersection<>(dsso); + inter.intersect(tupleSketch()); + try { inter.intersect(thetaSketch(123L, 10), factory.newSummary()); fail(); } + catch (final SketchesArgumentException e) { } + inter.intersect(thetaSketch(9001L, 10), factory.newSummary()); //default seed + assertEquals(inter.getResult().getRetainedEntries(), 10); + } + + @Test + public void checkAnotB() { + final TupleAnotB<DoubleSummary> anotb = new TupleAnotB<>(); + anotb.setA(tupleSketch()); + try { anotb.notB(thetaSketch(123L, 10)); fail(); } + catch (final SketchesArgumentException e) { } + anotb.notB(thetaSketch(123L, 0)); //empty is ignored + anotb.notB(thetaSketch(9001L, 5)); //default seed + assertEquals(anotb.getResult(true).getRetainedEntries(), 5); + + try { TupleAnotB.aNotB(tupleSketch(), thetaSketch(123L, 10)); fail(); } + catch (final SketchesArgumentException e) { } + assertEquals(TupleAnotB.aNotB(tupleSketch(), thetaSketch(9001L, 5)).getRetainedEntries(), 5); + } + +} --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
