This is an automated email from the ASF dual-hosted git repository. leerho pushed a commit to branch tuple-custom-seed in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 212cc54f53c469cf9a58fbc8bc718040aebfdf45 Author: Lee Rhodes <[email protected]> AuthorDate: Thu Oct 29 14:03:48 2026 -0700 Tuple: support custom update seeds, and check seed hashes Java tuple sketches always hashed with the default seed, wrote a fixed seed hash, and never checked the seed hash when reading an image or combining sketches. C++, Go and Rust support custom seeds and reject mismatches. All API changes are additive overloads: - UpdatableTupleSketchBuilder.setSeed(), and a seed constructor on UpdatableTupleSketch, DoubleTupleSketch, IntegerTupleSketch, ArrayOfStringsTupleSketch and FdtSketch. - Seed constructors on TupleUnion, TupleIntersection and TupleAnotB, and seed overloads of the static TupleAnotB.aNotB methods and of the tuple JaccardSimilarity methods. - TupleSketch.heapifySketch(seg, deserializer, seed) and TupleSketch.getSeedHash(). Behavior: - Compact images record the sketch's seed hash (zero when empty, as in theta). Default-seed images are byte-for-byte unchanged. - Reading a non-empty compact image checks its seed hash. - Set operations check the seed hash of non-empty tuple and theta inputs, and their results carry the operation's seed hash. - The deprecated updatable form has no seed hash, so it is read as the default seed, and serializing an updatable sketch with a custom seed throws; compact() it first. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- .../org/apache/datasketches/fdt/FdtSketch.java | 11 + .../datasketches/tuple/CompactTupleSketch.java | 24 +- .../java/org/apache/datasketches/tuple/Filter.java | 7 +- .../datasketches/tuple/JaccardSimilarity.java | 244 +++++++++++++++++++-- .../datasketches/tuple/QuickSelectSketch.java | 47 +++- .../org/apache/datasketches/tuple/TupleAnotB.java | 101 +++++++-- .../datasketches/tuple/TupleIntersection.java | 21 +- .../org/apache/datasketches/tuple/TupleSketch.java | 42 +++- .../org/apache/datasketches/tuple/TupleUnion.java | 26 ++- .../datasketches/tuple/UpdatableTupleSketch.java | 36 ++- .../tuple/UpdatableTupleSketchBuilder.java | 20 +- .../java/org/apache/datasketches/tuple/Util.java | 23 +- .../tuple/adouble/DoubleTupleSketch.java | 20 ++ .../tuple/aninteger/IntegerTupleSketch.java | 20 ++ .../tuple/strings/ArrayOfStringsTupleSketch.java | 14 ++ .../tuple/CompactSketchWithDoubleSummaryTest.java | 4 +- .../datasketches/tuple/TupleCustomSeedTest.java | 243 ++++++++++++++++++++ 17 files changed, 821 insertions(+), 82 deletions(-) diff --git a/src/main/java/org/apache/datasketches/fdt/FdtSketch.java b/src/main/java/org/apache/datasketches/fdt/FdtSketch.java index fb9f5c752..f33267fef 100644 --- a/src/main/java/org/apache/datasketches/fdt/FdtSketch.java +++ b/src/main/java/org/apache/datasketches/fdt/FdtSketch.java @@ -22,6 +22,7 @@ package org.apache.datasketches.fdt; import java.lang.foreign.MemorySegment; import java.util.List; +import org.apache.datasketches.common.ResizeFactor; import org.apache.datasketches.common.SketchesArgumentException; import org.apache.datasketches.thetacommon.ThetaUtil; import org.apache.datasketches.tuple.strings.ArrayOfStringsTupleSketch; @@ -57,6 +58,16 @@ public final class FdtSketch extends ArrayOfStringsTupleSketch { super(lgK); } + /** + * Create new instance of Frequent Distinct Tuples sketch with the given + * Log-base2 of required nominal entries and the given update seed. + * @param lgK Log-base2 of required nominal entries. + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + */ + public FdtSketch(final int lgK, final long seed) { + super(lgK, ResizeFactor.X8, 1.0F, seed); + } + /** * Used by deserialization. * @param seg the image of a FdtSketch diff --git a/src/main/java/org/apache/datasketches/tuple/CompactTupleSketch.java b/src/main/java/org/apache/datasketches/tuple/CompactTupleSketch.java index 4c2ed8ef6..34e95f636 100644 --- a/src/main/java/org/apache/datasketches/tuple/CompactTupleSketch.java +++ b/src/main/java/org/apache/datasketches/tuple/CompactTupleSketch.java @@ -22,6 +22,9 @@ package org.apache.datasketches.tuple; import static java.lang.foreign.ValueLayout.JAVA_BYTE; import static java.lang.foreign.ValueLayout.JAVA_INT_UNALIGNED; import static java.lang.foreign.ValueLayout.JAVA_LONG_UNALIGNED; +import static java.lang.foreign.ValueLayout.JAVA_SHORT_UNALIGNED; +import static org.apache.datasketches.common.Util.checkSeedHashes; +import static org.apache.datasketches.common.Util.computeSeedHash; import static org.apache.datasketches.thetacommon.HashOperations.count; import java.lang.foreign.MemorySegment; @@ -45,7 +48,6 @@ public final class CompactTupleSketch<S extends Summary> extends TupleSketch<S> private static final byte serialVersionWithSummaryClassNameUID = 1; private static final byte serialVersionUIDLegacy = 2; private static final byte serialVersionUID = 3; - private static final short defaultSeedHash = (short) 37836; // for compatibility with C++ private final long[] hashArr_; private S[] summaryArr_; @@ -59,9 +61,11 @@ public final class CompactTupleSketch<S extends Summary> extends TupleSketch<S> * @param summaryArr compacted summary array * @param thetaLong long value of theta * @param empty empty flag + * @param seedHash the seed hash */ - CompactTupleSketch(final long[] hashArr, final S[] summaryArr, final long thetaLong, final boolean empty) { - super(thetaLong, empty, null); + CompactTupleSketch(final long[] hashArr, final S[] summaryArr, final long thetaLong, final boolean empty, + final short seedHash) { + super(thetaLong, empty, null, seedHash); super.thetaLong_ = thetaLong; super.empty_ = empty; hashArr_ = hashArr; @@ -73,9 +77,10 @@ public final class CompactTupleSketch<S extends Summary> extends TupleSketch<S> * * @param seg MemorySegment object with serialized CompactTupleSketch * @param deserializer the SummaryDeserializer + * @param seed the update seed that the serialized sketch must have been created with */ - CompactTupleSketch(final MemorySegment seg, final SummaryDeserializer<S> deserializer) { - super(Long.MAX_VALUE, true, null); + CompactTupleSketch(final MemorySegment seg, final SummaryDeserializer<S> deserializer, final long seed) { + super(Long.MAX_VALUE, true, null, computeSeedHash(seed)); int offset = 0; final byte preambleLongs = seg.get(JAVA_BYTE, offset++); final byte version = seg.get(JAVA_BYTE, offset++); @@ -87,9 +92,10 @@ public final class CompactTupleSketch<S extends Summary> extends TupleSketch<S> } SerializerDeserializer .validateType(seg.get(JAVA_BYTE, offset++), SerializerDeserializer.SketchType.CompactTupleSketch); - if (version <= serialVersionUIDLegacy) { // legacy serial format + if (version <= serialVersionUIDLegacy) { // legacy serial format, always written with the default seed final byte flags = seg.get(JAVA_BYTE, offset++); empty_ = (flags & (1 << FlagsLegacy.IS_EMPTY.ordinal())) > 0; + if (!empty_) { checkSeedHashes(seedHash_, Util.DEFAULT_SEED_HASH); } final boolean isThetaIncluded = (flags & (1 << FlagsLegacy.IS_THETA_INCLUDED.ordinal())) > 0; if (isThetaIncluded) { thetaLong_ = seg.get(JAVA_LONG_UNALIGNED, offset); @@ -124,8 +130,10 @@ public final class CompactTupleSketch<S extends Summary> extends TupleSketch<S> } else { // current serial format offset++; //skip unused byte final byte flags = seg.get(JAVA_BYTE, offset++); - offset += 2; //skip 2 unused bytes + final short seedHash = seg.get(JAVA_SHORT_UNALIGNED, offset); + offset += Short.BYTES; empty_ = (flags & (1 << Flags.IS_EMPTY.ordinal())) > 0; + if (!empty_) { checkSeedHashes(seedHash_, seedHash); } // an empty image carries zero, as in theta thetaLong_ = Long.MAX_VALUE; int count = 0; if (!empty_) { @@ -221,7 +229,7 @@ public final class CompactTupleSketch<S extends Summary> extends TupleSketch<S> | (1 << Flags.IS_READ_ONLY.ordinal()) | (isEmpty() ? 1 << Flags.IS_EMPTY.ordinal() : 0) ); - ByteArrayUtil.putShortLE(bytes, offset, isEmpty() ? 0 : defaultSeedHash); // empty image carries zero, as in theta + ByteArrayUtil.putShortLE(bytes, offset, isEmpty() ? 0 : seedHash_); // empty image carries zero, as in theta offset += Short.BYTES; if (!isEmpty()) { if (!isSingleItem) { diff --git a/src/main/java/org/apache/datasketches/tuple/Filter.java b/src/main/java/org/apache/datasketches/tuple/Filter.java index 8706043c1..aaab7977a 100644 --- a/src/main/java/org/apache/datasketches/tuple/Filter.java +++ b/src/main/java/org/apache/datasketches/tuple/Filter.java @@ -50,7 +50,7 @@ public class Filter<T extends Summary> { @SuppressWarnings("unchecked") public CompactTupleSketch<T> filter(final TupleSketch<T> sketchIn) { if (sketchIn == null) { - return new CompactTupleSketch<>(null, null, Long.MAX_VALUE, true); + return new CompactTupleSketch<>(null, null, Long.MAX_VALUE, true, Util.DEFAULT_SEED_HASH); } final long[] hashes = new long[sketchIn.getRetainedEntries()]; T[] summaries = null; // lazy init to get class from the first entry @@ -68,9 +68,10 @@ public class Filter<T extends Summary> { } final boolean isEmpty = i == 0 && !sketchIn.isEstimationMode(); if (i == 0) { - return new CompactTupleSketch<>(null, null, sketchIn.getThetaLong(), isEmpty); + return new CompactTupleSketch<>(null, null, sketchIn.getThetaLong(), isEmpty, sketchIn.getSeedHash()); } - return new CompactTupleSketch<>(Arrays.copyOf(hashes, i), Arrays.copyOf(summaries, i), sketchIn.getThetaLong(), isEmpty); + return new CompactTupleSketch<>(Arrays.copyOf(hashes, i), Arrays.copyOf(summaries, i), + sketchIn.getThetaLong(), isEmpty, sketchIn.getSeedHash()); } } diff --git a/src/main/java/org/apache/datasketches/tuple/JaccardSimilarity.java b/src/main/java/org/apache/datasketches/tuple/JaccardSimilarity.java index 421df0131..0f4a3d0a8 100644 --- a/src/main/java/org/apache/datasketches/tuple/JaccardSimilarity.java +++ b/src/main/java/org/apache/datasketches/tuple/JaccardSimilarity.java @@ -21,6 +21,7 @@ package org.apache.datasketches.tuple; 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.BoundsOnRatiosInTupleSketchedSets.getEstimateOfBoverA; import static org.apache.datasketches.thetacommon.BoundsOnRatiosInTupleSketchedSets.getLowerBoundForBoverA; @@ -69,20 +70,47 @@ public final class JaccardSimilarity { final TupleSketch<S> sketchA, final TupleSketch<S> sketchB, final SummarySetOperations<S> summarySetOps) { + return jaccard(sketchA, sketchB, summarySetOps, DEFAULT_UPDATE_SEED); + } + + /** + * Computes the Jaccard similarity index with upper and lower bounds. The Jaccard similarity index + * <i>J(A,B) = (A ^ B)/(A U B)</i> is used to measure how similar the two sketches are to each + * other. If J = 1.0, the sketches are considered equal. If J = 0, the two sketches are + * distinct from each other. A Jaccard of .95 means the overlap between the two + * populations is 95% of the union of the two populations. + * + * <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. + * + * @param sketchA The first argument, a TupleSketch with summary type <i>S</i> + * @param sketchB The second argument, a TupleSketch with summary type <i>S</i> + * @param summarySetOps instance of SummarySetOperations used to unify or intersect summaries. + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + * @param <S> Summary + * @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. + * @throws SketchesArgumentException if the seed hash of a non-empty sketch does not match the given seed + */ + public static <S extends Summary> double[] jaccard( + final TupleSketch<S> sketchA, + final TupleSketch<S> sketchB, + final SummarySetOperations<S> summarySetOps, + 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 TupleSketch<S> unionAB = computeUnion(sketchA, sketchB, summarySetOps); + final TupleSketch<S> unionAB = computeUnion(sketchA, sketchB, summarySetOps, seed); if (identicalSets(sketchA.getRetainedEntries(), sketchA.getThetaLong(), sketchB.getRetainedEntries(), sketchB.getThetaLong(), unionAB)) { return ONES.clone(); } //Create the TupleIntersection - final TupleIntersection<S> inter = new TupleIntersection<>(summarySetOps); + final TupleIntersection<S> inter = new TupleIntersection<>(summarySetOps, seed); inter.intersect(sketchA); inter.intersect(sketchB); inter.intersect(unionAB); //ensures that intersection is a subset of the union @@ -117,6 +145,35 @@ public final class JaccardSimilarity { final TupleSketch<S> sketchA, final ThetaSketch sketchB, final S summary, final SummarySetOperations<S> summarySetOps) { + return jaccard(sketchA, sketchB, summary, summarySetOps, DEFAULT_UPDATE_SEED); + } + + /** + * Computes the Jaccard similarity index with upper and lower bounds. The Jaccard similarity index + * <i>J(A,B) = (A ^ B)/(A U B)</i> is used to measure how similar the two sketches are to each + * other. If J = 1.0, the sketches are considered equal. If J = 0, the two sketches are + * distinct from each other. A Jaccard of .95 means the overlap between the two + * populations is 95% of the union of the two populations. + * + * <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. + * + * @param sketchA The first argument, a TupleSketch with summary type <i>S</i> + * @param sketchB The second argument, a ThetaSketch + * @param summary the given proxy summary for the ThetaSketch, which doesn't have one. + * This may not be null. + * @param summarySetOps instance of SummarySetOperations used to unify or intersect summaries. + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + * @param <S> Summary + * @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. + * @throws SketchesArgumentException if the seed hash of a non-empty sketch does not match the given seed + */ + public static <S extends Summary> double[] jaccard( + final TupleSketch<S> sketchA, + final ThetaSketch sketchB, + final S summary, final SummarySetOperations<S> summarySetOps, + final long seed) { // Null case checks if (summary == null) { throw new SketchesArgumentException("Summary cannot be null."); } @@ -126,14 +183,14 @@ public final class JaccardSimilarity { if (sketchA.isEmpty() && sketchB.isEmpty()) { return ONES.clone(); } if (sketchA.isEmpty() || sketchB.isEmpty()) { return ZEROS.clone(); } - final TupleSketch<S> unionAB = computeUnion(sketchA, sketchB, summary, summarySetOps); + final TupleSketch<S> unionAB = computeUnion(sketchA, sketchB, summary, summarySetOps, seed); if (identicalSets(sketchA.getRetainedEntries(), sketchA.getThetaLong(), sketchB.getRetainedEntries(true), sketchB.getThetaLong(), unionAB)) { return ONES.clone(); } //Create the Tuple/Theta Intersection - final TupleIntersection<S> inter = new TupleIntersection<>(summarySetOps); + final TupleIntersection<S> inter = new TupleIntersection<>(summarySetOps, seed); inter.intersect(sketchA); inter.intersect(sketchB, summary); inter.intersect(unionAB); //ensures that intersection is a subset of the union @@ -159,13 +216,33 @@ public final class JaccardSimilarity { final TupleSketch<S> sketchA, final TupleSketch<S> sketchB, final SummarySetOperations<S> summarySetOps) { + return exactlyEqual(sketchA, sketchB, summarySetOps, DEFAULT_UPDATE_SEED); + } + + /** + * Returns true if the two given sketches have exactly the same hash values and the same + * theta values. Thus, they are equivalent. + * @param sketchA The first argument, a TupleSketch with summary type <i>S</i> + * @param sketchB The second argument, a TupleSketch with summary type <i>S</i> + * @param summarySetOps instance of SummarySetOperations used to unify or intersect summaries. + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + * @param <S> Summary + * @return true if the two given sketches have exactly the same hash values and the same + * theta values. + * @throws SketchesArgumentException if the seed hash of a non-empty sketch does not match the given seed + */ + public static <S extends Summary> boolean exactlyEqual( + final TupleSketch<S> sketchA, + final TupleSketch<S> sketchB, + final SummarySetOperations<S> summarySetOps, + 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 TupleSketch<S> unionAB = computeUnion(sketchA, sketchB, summarySetOps); + final TupleSketch<S> unionAB = computeUnion(sketchA, sketchB, summarySetOps, seed); return identicalSets(sketchA.getRetainedEntries(), sketchA.getThetaLong(), sketchB.getRetainedEntries(), sketchB.getThetaLong(), unionAB); } @@ -186,6 +263,28 @@ public final class JaccardSimilarity { final TupleSketch<S> sketchA, final ThetaSketch sketchB, final S summary, final SummarySetOperations<S> summarySetOps) { + return exactlyEqual(sketchA, sketchB, summary, summarySetOps, DEFAULT_UPDATE_SEED); + } + + /** + * Returns true if the two given sketches have exactly the same hash values and the same + * theta values. Thus, they are equivalent. + * @param sketchA The first argument, a TupleSketch with summary type <i>S</i> + * @param sketchB The second argument, a ThetaSketch + * @param summary the given proxy summary for the ThetaSketch, which doesn't have one. + * This may not be null. + * @param summarySetOps instance of SummarySetOperations used to unify or intersect summaries. + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + * @param <S> Summary + * @return true if the two given sketches have exactly the same hash values and the same + * theta values. + * @throws SketchesArgumentException if the seed hash of a non-empty sketch does not match the given seed + */ + public static <S extends Summary> boolean exactlyEqual( + final TupleSketch<S> sketchA, + final ThetaSketch sketchB, + final S summary, final SummarySetOperations<S> summarySetOps, + final long seed) { // Null case checks if (summary == null) { throw new SketchesArgumentException("Summary cannot be null."); } @@ -195,7 +294,7 @@ public final class JaccardSimilarity { if (sketchA.isEmpty() && sketchB.isEmpty()) { return true; } if (sketchA.isEmpty() || sketchB.isEmpty()) { return false; } - final TupleSketch<S> unionAB = computeUnion(sketchA, sketchB, summary, summarySetOps); + final TupleSketch<S> unionAB = computeUnion(sketchA, sketchB, summary, summarySetOps, seed); return identicalSets(sketchA.getRetainedEntries(), sketchA.getThetaLong(), sketchB.getRetainedEntries(true), sketchB.getThetaLong(), unionAB); } @@ -219,10 +318,35 @@ public final class JaccardSimilarity { final TupleSketch<S> measured, final TupleSketch<S> expected, final SummarySetOperations<S> summarySetOps, final double threshold) { + return similarityTest(measured, expected, summarySetOps, threshold, DEFAULT_UPDATE_SEED); + } + + /** + * Tests similarity of a measured TupleSketch against an expected TupleSketch. + * Computes the lower bound of the Jaccard index <i>J<sub>LB</sub></i> of the measured and + * expected sketches. + * if <i>J<sub>LB</sub> ≥ threshold</i>, then the sketches are considered to be + * similar with a confidence of 97.7%. + * + * @param measured a TupleSketch with summary type <i>S</i> to be tested + * @param expected the reference TupleSketch with summary type <i>S</i> that is considered to be correct. + * @param summarySetOps instance of SummarySetOperations used to unify or intersect summaries. + * @param threshold a real value between zero and one. + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + * @param <S> Summary + * @return if true, the similarity of the two sketches is greater than the given threshold + * with at least 97.7% confidence. + * @throws SketchesArgumentException if the seed hash of a non-empty sketch does not match the given seed + */ + public static <S extends Summary> boolean similarityTest( + final TupleSketch<S> measured, final TupleSketch<S> expected, + final SummarySetOperations<S> summarySetOps, + 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, summarySetOps)[0]; //choosing the lower bound + final double jRatioLB = jaccard(measured, expected, summarySetOps, seed)[0]; //choosing the lower bound return jRatioLB >= threshold; } @@ -247,10 +371,37 @@ public final class JaccardSimilarity { final TupleSketch<S> measured, final ThetaSketch expected, final S summary, final SummarySetOperations<S> summarySetOps, final double threshold) { + return similarityTest(measured, expected, summary, summarySetOps, threshold, DEFAULT_UPDATE_SEED); + } + + /** + * Tests similarity of a measured TupleSketch against an expected ThetaSketch. + * Computes the lower bound of the Jaccard index <i>J<sub>LB</sub></i> of the measured and + * expected sketches. + * if <i>J<sub>LB</sub> ≥ threshold</i>, then the sketches are considered to be + * similar with a confidence of 97.7%. + * + * @param measured a TupleSketch with summary type <i>S</i> to be tested + * @param expected the reference ThetaSketch that is considered to be correct. + * @param summary the given proxy summary for the ThetaSketch, which doesn't have one. + * This may not be null. + * @param summarySetOps instance of SummarySetOperations used to unify or intersect summaries. + * @param threshold a real value between zero and one. + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + * @param <S> Summary + * @return if true, the similarity of the two sketches is greater than the given threshold + * with at least 97.7% confidence. + * @throws SketchesArgumentException if the seed hash of a non-empty sketch does not match the given seed + */ + public static <S extends Summary> boolean similarityTest( + final TupleSketch<S> measured, final ThetaSketch expected, + final S summary, final SummarySetOperations<S> summarySetOps, + 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, summary, summarySetOps)[0]; //choosing the lower bound + final double jRatioLB = jaccard(measured, expected, summary, summarySetOps, seed)[0]; //choosing the lower bound return jRatioLB >= threshold; } @@ -273,10 +424,35 @@ public final class JaccardSimilarity { final TupleSketch<S> measured, final TupleSketch<S> expected, final SummarySetOperations<S> summarySetOps, final double threshold) { + return dissimilarityTest(measured, expected, summarySetOps, threshold, DEFAULT_UPDATE_SEED); + } + + /** + * Tests dissimilarity of a measured TupleSketch against an expected TupleSketch. + * Computes the upper bound of the Jaccard index <i>J<sub>UB</sub></i> of the measured and + * expected sketches. + * if <i>J<sub>UB</sub> ≤ threshold</i>, then the sketches are considered to be + * dissimilar with a confidence of 97.7%. + * + * @param measured a TupleSketch with summary type <i>S</i> to be tested + * @param expected the reference TupleSketch that is considered to be correct. + * @param summarySetOps instance of SummarySetOperations used to unify or intersect summaries. + * @param threshold a real value between zero and one. + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + * @param <S> Summary + * @return if true, the dissimilarity of the two sketches is greater than the given threshold + * with at least 97.7% confidence. + * @throws SketchesArgumentException if the seed hash of a non-empty sketch does not match the given seed + */ + public static <S extends Summary> boolean dissimilarityTest( + final TupleSketch<S> measured, final TupleSketch<S> expected, + final SummarySetOperations<S> summarySetOps, + 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, summarySetOps)[2]; //choosing the upper bound + final double jRatioUB = jaccard(measured, expected, summarySetOps, seed)[2]; //choosing the upper bound return jRatioUB <= threshold; } @@ -301,47 +477,78 @@ public final class JaccardSimilarity { final TupleSketch<S> measured, final ThetaSketch expected, final S summary, final SummarySetOperations<S> summarySetOps, final double threshold) { + return dissimilarityTest(measured, expected, summary, summarySetOps, threshold, DEFAULT_UPDATE_SEED); + } + + /** + * Tests dissimilarity of a measured TupleSketch against an expected ThetaSketch. + * Computes the upper bound of the Jaccard index <i>J<sub>UB</sub></i> of the measured and + * expected sketches. + * if <i>J<sub>UB</sub> ≤ threshold</i>, then the sketches are considered to be + * dissimilar with a confidence of 97.7%. + * + * @param measured a TupleSketch with summary type <i>S</i> to be tested + * @param expected the reference ThetaSketch that is considered to be correct. + * @param summary the given proxy summary for the ThetaSketch, which doesn't have one. + * This may not be null. + * @param summarySetOps instance of SummarySetOperations used to unify or intersect summaries. + * @param threshold a real value between zero and one. + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + * @param <S> Summary + * @return if true, the dissimilarity of the two sketches is greater than the given threshold + * with at least 97.7% confidence. + * @throws SketchesArgumentException if the seed hash of a non-empty sketch does not match the given seed + */ + public static <S extends Summary> boolean dissimilarityTest( + final TupleSketch<S> measured, final ThetaSketch expected, + final S summary, final SummarySetOperations<S> summarySetOps, + 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, summary, summarySetOps)[2]; //choosing the upper bound + final double jRatioUB = jaccard(measured, expected, summary, summarySetOps, seed)[2]; //choosing the upper bound return jRatioUB <= threshold; } /** - * Computes the union of the two given TupleSketches. See {@link #newUnion(int, SummarySetOperations)}. + * Computes the union of the two given TupleSketches. See {@link #newUnion(int, SummarySetOperations, long)}. * @param sketchA the given TupleSketch A * @param sketchB the given TupleSketch B * @param summarySetOps instance of SummarySetOperations used to unify summaries. + * @param seed the update seed * @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 SummarySetOperations<S> summarySetOps, + final long seed) { final TupleUnion<S> union = - newUnion(sketchA.getRetainedEntries() + sketchB.getRetainedEntries(), summarySetOps); + newUnion(sketchA.getRetainedEntries() + sketchB.getRetainedEntries(), summarySetOps, seed); union.union(sketchA); union.union(sketchB); return union.getResult(); } /** - * Computes the union of the given TupleSketch and ThetaSketch. See {@link #newUnion(int, SummarySetOperations)}. + * Computes the union of the given TupleSketch and ThetaSketch. See {@link #newUnion(int, SummarySetOperations, long)}. * @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 seed the update seed * @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 S summary, final SummarySetOperations<S> summarySetOps, + final long seed) { final TupleUnion<S> union = - newUnion(sketchA.getRetainedEntries() + sketchB.getRetainedEntries(true), summarySetOps); + newUnion(sketchA.getRetainedEntries() + sketchB.getRetainedEntries(true), summarySetOps, seed); union.union(sketchA); union.union(sketchB, summary); return union.getResult(); @@ -352,15 +559,16 @@ public final class JaccardSimilarity { * 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 seed the update seed * @param <S> Summary * @return a new TupleUnion */ private static <S extends Summary> TupleUnion<S> newUnion( - final int totalCount, final SummarySetOperations<S> summarySetOps) { + final int totalCount, final SummarySetOperations<S> summarySetOps, final long seed) { 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); + return new TupleUnion<>(newK, summarySetOps, seed); } /** diff --git a/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java b/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java index 64548d6c1..2b90fd4a3 100644 --- a/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java +++ b/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java @@ -37,6 +37,7 @@ import org.apache.datasketches.common.Family; import org.apache.datasketches.common.QuickSelect; import org.apache.datasketches.common.ResizeFactor; import org.apache.datasketches.common.SketchesArgumentException; +import org.apache.datasketches.common.SketchesStateException; import org.apache.datasketches.thetacommon.HashOperations; import org.apache.datasketches.thetacommon.ThetaUtil; @@ -112,12 +113,32 @@ class QuickSelectSketch<S extends Summary> extends TupleSketch<S> { final int lgResizeFactor, final float samplingProbability, final SummaryFactory<S> summaryFactory) { + this(nomEntries, lgResizeFactor, samplingProbability, summaryFactory, Util.DEFAULT_SEED_HASH); + } + + /** + * This is to create a new instance of a QuickSelectSketch with custom resize factor, sampling + * probability and seed hash + * @param nomEntries Nominal number of entries. Forced to the nearest power of 2 greater than + * or equal to the given value. + * @param lgResizeFactor log2(resizeFactor) - value from 0 to 3 + * @param samplingProbability the given sampling probability + * @param summaryFactory An instance of a SummaryFactory. + * @param seedHash the hash of the update seed + */ + QuickSelectSketch( + final int nomEntries, + final int lgResizeFactor, + final float samplingProbability, + final SummaryFactory<S> summaryFactory, + final short seedHash) { this( nomEntries, lgResizeFactor, samplingProbability, summaryFactory, - Util.getStartingCapacity(nomEntries, lgResizeFactor) + Util.getStartingCapacity(nomEntries, lgResizeFactor), + seedHash ); } @@ -128,18 +149,21 @@ class QuickSelectSketch<S extends Summary> extends TupleSketch<S> { * @param samplingProbability the given sampling probability * @param summaryFactory An instance of a SummaryFactory. * @param startingSize starting size of the sketch. + * @param seedHash the hash of the update seed */ private QuickSelectSketch( final int nomEntries, final int lgResizeFactor, final float samplingProbability, final SummaryFactory<S> summaryFactory, - final int startingSize) { + final int startingSize, + final short seedHash) { final long thetaLong = (long) (Long.MAX_VALUE * (double) samplingProbability); super( thetaLong, true, - summaryFactory); + summaryFactory, + seedHash); nomEntries_ = ceilingPowerOf2(nomEntries); lgResizeFactor_ = lgResizeFactor; samplingProbability_ = samplingProbability; @@ -158,7 +182,8 @@ class QuickSelectSketch<S extends Summary> extends TupleSketch<S> { super( sketch.thetaLong_, sketch.empty_, - sketch.summaryFactory_); + sketch.summaryFactory_, + sketch.seedHash_); nomEntries_ = sketch.nomEntries_; lgResizeFactor_ = sketch.lgResizeFactor_; samplingProbability_ = sketch.samplingProbability_; @@ -194,7 +219,7 @@ class QuickSelectSketch<S extends Summary> extends TupleSketch<S> { rebuildThreshold_ = val.myRebuildThreshold; hashTable_ = val.myHashTable; summaryTable_ = val.mySummaryTable; - super(thetaLong, val.myEmpty, summaryFactory); + super(thetaLong, val.myEmpty, summaryFactory, Util.DEFAULT_SEED_HASH); //this form has no seed hash } private static final class Validate<S> { @@ -379,8 +404,8 @@ class QuickSelectSketch<S extends Summary> extends TupleSketch<S> { @SuppressWarnings("unchecked") public CompactTupleSketch<S> compact() { if (getRetainedEntries() == 0) { - if (empty_) { return new CompactTupleSketch<>(null, null, Long.MAX_VALUE, true); } - return new CompactTupleSketch<>(null, null, thetaLong_, false); + if (empty_) { return new CompactTupleSketch<>(null, null, Long.MAX_VALUE, true, seedHash_); } + return new CompactTupleSketch<>(null, null, thetaLong_, false, seedHash_); } final long[] hashArr = new long[getRetainedEntries()]; final S[] summaryArr = Util.newSummaryArray(summaryTable_, getRetainedEntries()); @@ -392,7 +417,7 @@ class QuickSelectSketch<S extends Summary> extends TupleSketch<S> { i++; } } - return new CompactTupleSketch<>(hashArr, summaryArr, thetaLong_, empty_); + return new CompactTupleSketch<>(hashArr, summaryArr, thetaLong_, empty_, seedHash_); } // Layout of first 8 bytes: @@ -406,10 +431,16 @@ class QuickSelectSketch<S extends Summary> extends TupleSketch<S> { * @deprecated As of 3.0.0, serializing an UpdatableTupleSketch is deprecated. * This capability will be removed in a future release. * Serializing a CompactTupleSketch is not deprecated. + * @throws SketchesStateException if this sketch was created with a custom seed, + * because this serialized form has no seed hash. Use compact().toByteArray() instead. */ @Deprecated @Override public byte[] toByteArray() { + if (seedHash_ != Util.DEFAULT_SEED_HASH) { + throw new SketchesStateException("An updatable sketch created with a custom seed cannot be serialized, " + + "because this serialized form has no seed hash. Use compact().toByteArray() instead."); + } byte[][] summariesBytes = null; int summariesBytesLength = 0; if (retEntries_ > 0) { diff --git a/src/main/java/org/apache/datasketches/tuple/TupleAnotB.java b/src/main/java/org/apache/datasketches/tuple/TupleAnotB.java index e10a27a47..2f5776c82 100644 --- a/src/main/java/org/apache/datasketches/tuple/TupleAnotB.java +++ b/src/main/java/org/apache/datasketches/tuple/TupleAnotB.java @@ -20,6 +20,8 @@ package org.apache.datasketches.tuple; import static java.lang.Math.min; +import static org.apache.datasketches.common.Util.DEFAULT_UPDATE_SEED; +import static org.apache.datasketches.common.Util.computeSeedHash; import static org.apache.datasketches.common.Util.exactLog2OfLong; import static org.apache.datasketches.thetacommon.HashOperations.convertToHashTable; import static org.apache.datasketches.thetacommon.HashOperations.hashSearch; @@ -70,6 +72,7 @@ import org.apache.datasketches.thetacommon.ThetaUtil; * @author Lee Rhodes */ public final class TupleAnotB<S extends Summary> { + private final short seedHash_; private boolean empty_ = true; private long thetaLong_ = Long.MAX_VALUE; private long[] hashArr_ = null; //always in compact form, not necessarily sorted @@ -88,9 +91,19 @@ public final class TupleAnotB<S extends Summary> { } /** - * No argument constructor. + * No argument constructor. The inputs must have been created with the default update seed. */ - public TupleAnotB() { } + public TupleAnotB() { + this(DEFAULT_UPDATE_SEED); + } + + /** + * Creates a TupleAnotB for sketches that were created with the given update seed. + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + */ + public TupleAnotB(final long seed) { + seedHash_ = computeSeedHash(seed); + } /** * This is part of a multistep, stateful TupleAnotB operation and sets the given TupleSketch as the @@ -122,6 +135,7 @@ public final class TupleAnotB<S extends Summary> { reset(); throw new SketchesArgumentException("The input argument <i>A</i> may not be null"); } + Util.checkTupleSeedHash(skA, seedHash_); empty_ = skA.isEmpty(); thetaLong_ = skA.getThetaLong(); @@ -150,6 +164,7 @@ public final class TupleAnotB<S extends Summary> { */ public void notB(final TupleSketch<S> skB) { if (skB == null) { return; } //ignore + Util.checkTupleSeedHash(skB, seedHash_); final long thetaLongB = skB.getThetaLong(); final int countB = skB.getRetainedEntries(); @@ -222,7 +237,7 @@ public final class TupleAnotB<S extends Summary> { */ public void notB(final ThetaSketch skB) { if (skB == null) { return; } //ignore - Util.checkThetaSeedHash(skB); + Util.checkThetaSeedHash(skB, seedHash_); final long thetaLongB = skB.getThetaLong(); final int countB = skB.getRetainedEntries(); @@ -285,10 +300,11 @@ public final class TupleAnotB<S extends Summary> { public CompactTupleSketch<S> getResult(final boolean reset) { final CompactTupleSketch<S> result; if (curCount_ == 0) { - result = new CompactTupleSketch<>(null, null, thetaLong_, thetaLong_ == Long.MAX_VALUE); + result = new CompactTupleSketch<>(null, null, thetaLong_, thetaLong_ == Long.MAX_VALUE, seedHash_); } else { - result = new CompactTupleSketch<>(hashArr_, Util.copySummaryArray(summaryArr_), thetaLong_, false); + result = new CompactTupleSketch<>(hashArr_, Util.copySummaryArray(summaryArr_), thetaLong_, false, + seedHash_); } if (reset) { reset(); } return result; @@ -322,9 +338,32 @@ public final class TupleAnotB<S extends Summary> { public static <S extends Summary> CompactTupleSketch<S> aNotB( final TupleSketch<S> skA, final TupleSketch<S> skB) { + return aNotB(skA, skB, DEFAULT_UPDATE_SEED); + } + + /** + * Returns the A-and-not-B set operation on a TupleSketch and a TupleSketch, which were created with the given + * update seed. Otherwise, this is the same as {@link #aNotB(TupleSketch, TupleSketch)}. + * + * @param skA The incoming TupleSketch for the first argument + * @param skB The incoming TupleSketch for the second argument + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + * @param <S> Type of Summary + * @return the result as an unordered {@link CompactTupleSketch} + * @throws SketchesArgumentException if the seed hash of a non-empty argument does not match the given seed + */ + @SuppressFBWarnings(value = "UWF_FIELD_NOT_INITIALIZED_IN_CONSTRUCTOR", + justification = "hashArr and summaryArr are guaranteed to be valid due to the switch on CornerCase") + public static <S extends Summary> CompactTupleSketch<S> aNotB( + final TupleSketch<S> skA, + final TupleSketch<S> skB, + final long seed) { if (skA == null || skB == null) { throw new SketchesArgumentException("Neither argument may be null for this stateless operation."); } + final short seedHash = computeSeedHash(seed); + Util.checkTupleSeedHash(skA, seedHash); + Util.checkTupleSeedHash(skB, seedHash); final long thetaLongA = skA.getThetaLong(); final int countA = skA.getRetainedEntries(); @@ -343,16 +382,16 @@ public final class TupleAnotB<S extends Summary> { switch (anotbAction) { case EMPTY_1_0_T: { - result = new CompactTupleSketch<>(null, null, Long.MAX_VALUE, true); + result = new CompactTupleSketch<>(null, null, Long.MAX_VALUE, true, seedHash); break; } case DEGEN_MIN_0_F: { final long thetaLong = min(thetaLongA, thetaLongB); - result = new CompactTupleSketch<>(null, null, thetaLong, false); + result = new CompactTupleSketch<>(null, null, thetaLong, false, seedHash); break; } case DEGEN_THA_0_F: { - result = new CompactTupleSketch<>(null, null, thetaLongA, false); + result = new CompactTupleSketch<>(null, null, thetaLongA, false, seedHash); break; } case TRIM_A: { @@ -361,12 +400,12 @@ public final class TupleAnotB<S extends Summary> { final S[] summaryArrA = daA.summaryArr; final long minThetaLong = min(thetaLongA, thetaLongB); final DataArrays<S> da = trimAndCopyDataArrays(hashArrA, summaryArrA, minThetaLong, false); - result = new CompactTupleSketch<>(da.hashArr, da.summaryArr, minThetaLong, skA.empty_); + result = new CompactTupleSketch<>(da.hashArr, da.summaryArr, minThetaLong, skA.empty_, seedHash); break; } case SKETCH_A: { final DataArrays<S> daA = getCopyOfDataArraysTuple(skA); - result = new CompactTupleSketch<>(daA.hashArr, daA.summaryArr, thetaLongA, skA.empty_); + result = new CompactTupleSketch<>(daA.hashArr, daA.summaryArr, thetaLongA, skA.empty_, seedHash); break; } case FULL_ANOTB: { //both A and B should have valid entries. @@ -376,9 +415,9 @@ public final class TupleAnotB<S extends Summary> { getCopyOfResultArraysTuple(minThetaLong, daA.hashArr.length, daA.hashArr, daA.summaryArr, skB); final int countR = (daR.hashArr == null) ? 0 : daR.hashArr.length; if (countR == 0) { - result = new CompactTupleSketch<>(null, null, minThetaLong, minThetaLong == Long.MAX_VALUE); + result = new CompactTupleSketch<>(null, null, minThetaLong, minThetaLong == Long.MAX_VALUE, seedHash); } else { - result = new CompactTupleSketch<>(daR.hashArr, daR.summaryArr, minThetaLong, false); + result = new CompactTupleSketch<>(daR.hashArr, daR.summaryArr, minThetaLong, false, seedHash); } } //default: not possible @@ -415,10 +454,32 @@ public final class TupleAnotB<S extends Summary> { public static <S extends Summary> CompactTupleSketch<S> aNotB( final TupleSketch<S> skA, final ThetaSketch skB) { + return aNotB(skA, skB, DEFAULT_UPDATE_SEED); + } + + /** + * Returns the A-and-not-B set operation on a TupleSketch and a ThetaSketch, which were created with the given + * update seed. Otherwise, this is the same as {@link #aNotB(TupleSketch, ThetaSketch)}. + * + * @param skA The incoming TupleSketch for the first argument + * @param skB The incoming ThetaSketch for the second argument + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + * @param <S> Type of Summary + * @return the result as an unordered {@link CompactTupleSketch} + * @throws SketchesArgumentException if the seed hash of a non-empty argument does not match the given seed + */ + @SuppressFBWarnings(value = "UWF_FIELD_NOT_INITIALIZED_IN_CONSTRUCTOR", + justification = "hashArr and summaryArr are guaranteed to be valid due to the switch on CornerCase") + public static <S extends Summary> CompactTupleSketch<S> aNotB( + final TupleSketch<S> skA, + final ThetaSketch skB, + final long seed) { if (skA == null || skB == null) { throw new SketchesArgumentException("Neither argument may be null for this stateless operation."); } - Util.checkThetaSeedHash(skB); + final short seedHash = computeSeedHash(seed); + Util.checkTupleSeedHash(skA, seedHash); + Util.checkThetaSeedHash(skB, seedHash); final long thetaLongA = skA.getThetaLong(); final int countA = skA.getRetainedEntries(); @@ -437,16 +498,16 @@ public final class TupleAnotB<S extends Summary> { switch (anotbAction) { case EMPTY_1_0_T: { - result = new CompactTupleSketch<>(null, null, Long.MAX_VALUE, true); + result = new CompactTupleSketch<>(null, null, Long.MAX_VALUE, true, seedHash); break; } case DEGEN_MIN_0_F: { final long thetaLong = min(thetaLongA, thetaLongB); - result = new CompactTupleSketch<>(null, null, thetaLong, false); + result = new CompactTupleSketch<>(null, null, thetaLong, false, seedHash); break; } case DEGEN_THA_0_F: { - result = new CompactTupleSketch<>(null, null, thetaLongA, false); + result = new CompactTupleSketch<>(null, null, thetaLongA, false, seedHash); break; } case TRIM_A: { @@ -455,12 +516,12 @@ public final class TupleAnotB<S extends Summary> { final S[] summaryArrA = daA.summaryArr; final long minThetaLong = min(thetaLongA, thetaLongB); final DataArrays<S> da = trimAndCopyDataArrays(hashArrA, summaryArrA, minThetaLong, false); - result = new CompactTupleSketch<>(da.hashArr, da.summaryArr, minThetaLong, skA.empty_); + result = new CompactTupleSketch<>(da.hashArr, da.summaryArr, minThetaLong, skA.empty_, seedHash); break; } case SKETCH_A: { final DataArrays<S> daA = getCopyOfDataArraysTuple(skA); - result = new CompactTupleSketch<>(daA.hashArr, daA.summaryArr, thetaLongA, skA.empty_); + result = new CompactTupleSketch<>(daA.hashArr, daA.summaryArr, thetaLongA, skA.empty_, seedHash); break; } case FULL_ANOTB: { //both A and B have valid entries. @@ -472,9 +533,9 @@ public final class TupleAnotB<S extends Summary> { getCopyOfResultArraysTheta(minThetaLong, daA.hashArr.length, daA.hashArr, daA.summaryArr, skB); final int countR = (daR.hashArr == null) ? 0 : daR.hashArr.length; if (countR == 0) { - result = new CompactTupleSketch<>(null, null, minThetaLong, minThetaLong == Long.MAX_VALUE); + result = new CompactTupleSketch<>(null, null, minThetaLong, minThetaLong == Long.MAX_VALUE, seedHash); } else { - result = new CompactTupleSketch<>(daR.hashArr, daR.summaryArr, minThetaLong, false); + result = new CompactTupleSketch<>(daR.hashArr, daR.summaryArr, minThetaLong, false, seedHash); } } //default: not possible diff --git a/src/main/java/org/apache/datasketches/tuple/TupleIntersection.java b/src/main/java/org/apache/datasketches/tuple/TupleIntersection.java index 3eb0a54d9..5aa61b81d 100644 --- a/src/main/java/org/apache/datasketches/tuple/TupleIntersection.java +++ b/src/main/java/org/apache/datasketches/tuple/TupleIntersection.java @@ -22,7 +22,9 @@ package org.apache.datasketches.tuple; import static java.lang.Math.ceil; 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.common.Util.computeSeedHash; import org.apache.datasketches.common.SketchesArgumentException; import org.apache.datasketches.common.SketchesStateException; @@ -43,6 +45,7 @@ import org.apache.datasketches.thetacommon.ThetaUtil; @SuppressWarnings("unchecked") public class TupleIntersection<S extends Summary> { private final SummarySetOperations<S> summarySetOps_; + private final short seedHash_; private boolean empty_; private long thetaLong_; private HashTables<S> hashTables_; @@ -53,7 +56,17 @@ public class TupleIntersection<S extends Summary> { * @param summarySetOps instance of SummarySetOperations */ public TupleIntersection(final SummarySetOperations<S> summarySetOps) { + this(summarySetOps, DEFAULT_UPDATE_SEED); + } + + /** + * Creates new TupleIntersection instance for sketches that were created with the given update seed. + * @param summarySetOps instance of SummarySetOperations + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + */ + public TupleIntersection(final SummarySetOperations<S> summarySetOps, final long seed) { summarySetOps_ = summarySetOps; + seedHash_ = computeSeedHash(seed); empty_ = false; // universal set at the start thetaLong_ = Long.MAX_VALUE; hashTables_ = new HashTables<>(); @@ -101,9 +114,11 @@ public class TupleIntersection<S extends Summary> { /** * Performs a stateful intersection of the internal set with the given TupleSketch. * @param tupleSketch input sketch to intersect with the internal state. It must not be null. + * @throws SketchesArgumentException if the seed hash of a non-empty sketch does not match this intersection */ public void intersect(final TupleSketch<S> tupleSketch) { if (tupleSketch == null) { throw new SketchesArgumentException("TupleSketch must not be null"); } + Util.checkTupleSeedHash(tupleSketch, seedHash_); final boolean firstCall = firstCall_; firstCall_ = false; @@ -150,7 +165,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); + Util.checkThetaSeedHash(thetaSketch, seedHash_); final boolean firstCall = firstCall_; firstCall_ = false; // input sketch is not null, could be first or next call @@ -196,7 +211,7 @@ public class TupleIntersection<S extends Summary> { } final int countIn = hashTables_.numKeys; if (countIn == 0) { - return new CompactTupleSketch<>(null, null, thetaLong_, empty_); + return new CompactTupleSketch<>(null, null, thetaLong_, empty_, seedHash_); } final int tableSize = hashTables_.hashTable.length; @@ -214,7 +229,7 @@ public class TupleIntersection<S extends Summary> { cnt++; } assert cnt == countIn; - return new CompactTupleSketch<>(hashArr, summaryArr, thetaLong_, empty_); + return new CompactTupleSketch<>(hashArr, summaryArr, thetaLong_, empty_, seedHash_); } /** diff --git a/src/main/java/org/apache/datasketches/tuple/TupleSketch.java b/src/main/java/org/apache/datasketches/tuple/TupleSketch.java index 7ef2ebc06..06d701edc 100644 --- a/src/main/java/org/apache/datasketches/tuple/TupleSketch.java +++ b/src/main/java/org/apache/datasketches/tuple/TupleSketch.java @@ -19,7 +19,9 @@ package org.apache.datasketches.tuple; +import static org.apache.datasketches.common.Util.DEFAULT_UPDATE_SEED; import static org.apache.datasketches.common.Util.LS; +import static org.apache.datasketches.common.Util.computeSeedHash; import java.lang.foreign.MemorySegment; @@ -41,11 +43,23 @@ public abstract class TupleSketch<S extends Summary> { long thetaLong_; boolean empty_ = true; protected SummaryFactory<S> summaryFactory_ = null; + final short seedHash_; - TupleSketch(final long thetaLong, final boolean empty, final SummaryFactory<S> summaryFactory) { + TupleSketch(final long thetaLong, final boolean empty, final SummaryFactory<S> summaryFactory, + final short seedHash) { this.thetaLong_ = thetaLong; this.empty_ = empty; this.summaryFactory_ = summaryFactory; + this.seedHash_ = seedHash; + } + + /** + * 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. + * @return the seed hash + */ + public short getSeedHash() { + return seedHash_; } /** @@ -252,11 +266,31 @@ public abstract class TupleSketch<S extends Summary> { public static <S extends Summary> TupleSketch<S> heapifySketch( final MemorySegment seg, final SummaryDeserializer<S> deserializer) { + return heapifySketch(seg, deserializer, DEFAULT_UPDATE_SEED); + } + + /** + * Instantiate a TupleSketch from a given MemorySegment, which was created with the given update seed. + * The seed hash of a non-empty compact image must match the given seed. + * An updatable image does not store a seed hash and must have been created with the default seed. + * @param <S> Type of Summary + * @param seg MemorySegment object representing a TupleSketch + * @param deserializer instance of SummaryDeserializer + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + * @return TupleSketch created from its MemorySegment representation + * @throws org.apache.datasketches.common.SketchesArgumentException if the seed hashes do not match + */ + public static <S extends Summary> TupleSketch<S> heapifySketch( + final MemorySegment seg, + final SummaryDeserializer<S> deserializer, + final long seed) { final SerializerDeserializer.SketchType sketchType = SerializerDeserializer.getSketchType(seg); if (sketchType == SerializerDeserializer.SketchType.QuickSelectSketch) { - return new QuickSelectSketch<>(seg, deserializer, null); + final QuickSelectSketch<S> sketch = new QuickSelectSketch<>(seg, deserializer, null); + Util.checkTupleSeedHash(sketch, computeSeedHash(seed)); + return sketch; } - return new CompactTupleSketch<>(seg, deserializer); + return new CompactTupleSketch<>(seg, deserializer, seed); } /** @@ -265,7 +299,7 @@ public abstract class TupleSketch<S extends Summary> { * @return an empty instance of a CompactTupleSketch */ public static <S extends Summary> TupleSketch<S> createEmptySketch() { - return new CompactTupleSketch<>(null, null, Long.MAX_VALUE, true); + return new CompactTupleSketch<>(null, null, Long.MAX_VALUE, true, Util.DEFAULT_SEED_HASH); } } diff --git a/src/main/java/org/apache/datasketches/tuple/TupleUnion.java b/src/main/java/org/apache/datasketches/tuple/TupleUnion.java index c052a6414..549ec8c13 100644 --- a/src/main/java/org/apache/datasketches/tuple/TupleUnion.java +++ b/src/main/java/org/apache/datasketches/tuple/TupleUnion.java @@ -20,8 +20,11 @@ package org.apache.datasketches.tuple; import static java.lang.Math.min; +import static org.apache.datasketches.common.Util.DEFAULT_UPDATE_SEED; +import static org.apache.datasketches.common.Util.computeSeedHash; import org.apache.datasketches.common.QuickSelect; +import org.apache.datasketches.common.ResizeFactor; import org.apache.datasketches.common.SketchesArgumentException; import org.apache.datasketches.theta.HashIterator; import org.apache.datasketches.theta.ThetaSketch; @@ -34,6 +37,7 @@ import org.apache.datasketches.thetacommon.ThetaUtil; */ public class TupleUnion<S extends Summary> { private final SummarySetOperations<S> summarySetOps_; + private final short seedHash_; private QuickSelectSketch<S> qsk_; private long unionThetaLong_; // need to maintain outside of the sketch private boolean empty_; @@ -54,8 +58,20 @@ public class TupleUnion<S extends Summary> { * @param summarySetOps instance of SummarySetOperations */ public TupleUnion(final int nomEntries, final SummarySetOperations<S> summarySetOps) { + this(nomEntries, summarySetOps, DEFAULT_UPDATE_SEED); + } + + /** + * Creates new TupleUnion instance for sketches that were created with the given update seed. + * @param nomEntries nominal entries (K). Forced to the nearest power of 2 greater than + * given value. + * @param summarySetOps instance of SummarySetOperations + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + */ + public TupleUnion(final int nomEntries, final SummarySetOperations<S> summarySetOps, final long seed) { summarySetOps_ = summarySetOps; - qsk_ = new QuickSelectSketch<>(nomEntries, null); + seedHash_ = computeSeedHash(seed); + qsk_ = new QuickSelectSketch<>(nomEntries, ResizeFactor.X8.lg(), 1f, null, seedHash_); unionThetaLong_ = qsk_.getThetaLong(); empty_ = true; } @@ -103,9 +119,11 @@ public class TupleUnion<S extends Summary> { * Performs a stateful union of the internal set with the given TupleSketch. * @param tupleSketch input tuple sketch to merge with the internal set. * Nulls and empty sketches are ignored. + * @throws SketchesArgumentException if the seed hash of a non-empty sketch does not match this union */ public void union(final TupleSketch<S> tupleSketch) { if (tupleSketch == null || tupleSketch.isEmpty()) { return; } + Util.checkTupleSeedHash(tupleSketch, seedHash_); empty_ = false; unionThetaLong_ = min(tupleSketch.thetaLong_, unionThetaLong_); final TupleSketchIterator<S> it = tupleSketch.iterator(); @@ -126,7 +144,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); + Util.checkThetaSeedHash(thetaSketch, seedHash_); empty_ = false; final long thetaIn = thetaSketch.getThetaLong(); unionThetaLong_ = min(thetaIn, unionThetaLong_); @@ -174,7 +192,7 @@ public class TupleUnion<S extends Summary> { if (numHashesIn == 0) { //numHashes == 0 && empty == false means Theta < 1.0 //Therefore, this is a degenerate sketch: theta < 1.0, count = 0, empty = false - result = new CompactTupleSketch<>(null, null, tmpThetaLong, empty_); + result = new CompactTupleSketch<>(null, null, tmpThetaLong, empty_, seedHash_); } else { @@ -209,7 +227,7 @@ public class TupleUnion<S extends Summary> { i++; } } - result = new CompactTupleSketch<>(hashArr, summaries, thetaLongOut, empty_); + result = new CompactTupleSketch<>(hashArr, summaries, thetaLongOut, empty_, seedHash_); } } if (reset) { reset(); } diff --git a/src/main/java/org/apache/datasketches/tuple/UpdatableTupleSketch.java b/src/main/java/org/apache/datasketches/tuple/UpdatableTupleSketch.java index 45bc88dcd..9fa84dc61 100644 --- a/src/main/java/org/apache/datasketches/tuple/UpdatableTupleSketch.java +++ b/src/main/java/org/apache/datasketches/tuple/UpdatableTupleSketch.java @@ -20,6 +20,7 @@ package org.apache.datasketches.tuple; import static org.apache.datasketches.common.Util.DEFAULT_UPDATE_SEED; +import static org.apache.datasketches.common.Util.computeSeedHash; import java.lang.foreign.MemorySegment; import java.nio.ByteBuffer; @@ -41,6 +42,7 @@ import org.apache.datasketches.hash.MurmurHash3; * @param <S> Type of the UpdatableSummary<U> */ public class UpdatableTupleSketch<U, S extends UpdatableSummary<U>> extends QuickSelectSketch<S> { + private final long seed_; /** * This is to create a new instance of an UpdatableQuickSelectSketch. @@ -59,7 +61,29 @@ public class UpdatableTupleSketch<U, S extends UpdatableSummary<U>> extends Quic */ public UpdatableTupleSketch(final int nomEntries, final int lgResizeFactor, final float samplingProbability, final SummaryFactory<S> summaryFactory) { - super(nomEntries, lgResizeFactor, samplingProbability, summaryFactory); + this(nomEntries, lgResizeFactor, samplingProbability, summaryFactory, DEFAULT_UPDATE_SEED); + } + + /** + * This is to create a new instance of an UpdatableQuickSelectSketch with the given update seed. + * @param nomEntries Nominal number of entries. Forced to the nearest power of 2 greater than + * or equal to the given value. + * @param lgResizeFactor log2(resizeFactor) - value from 0 to 3: + * <pre> + * 0 - no resizing (max size allocated), + * 1 - double internal hash table each time it reaches a threshold + * 2 - grow four times + * 3 - grow eight times (default) + * </pre> + * @param samplingProbability + * <a href="{@docRoot}/resources/dictionary.html#p">See Sampling Probability</a> + * @param summaryFactory An instance of a SummaryFactory. + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + */ + public UpdatableTupleSketch(final int nomEntries, final int lgResizeFactor, + final float samplingProbability, final SummaryFactory<S> summaryFactory, final long seed) { + super(nomEntries, lgResizeFactor, samplingProbability, summaryFactory, computeSeedHash(seed)); + seed_ = seed; } /** @@ -77,6 +101,7 @@ public class UpdatableTupleSketch<U, S extends UpdatableSummary<U>> extends Quic final SummaryDeserializer<S> deserializer, final SummaryFactory<S> summaryFactory) { super(srcSeg, deserializer, summaryFactory); + seed_ = DEFAULT_UPDATE_SEED; //this serialized form is always created with the default seed } /** @@ -85,6 +110,7 @@ public class UpdatableTupleSketch<U, S extends UpdatableSummary<U>> extends Quic */ public UpdatableTupleSketch(final UpdatableTupleSketch<U, S> sketch) { super(sketch); + seed_ = sketch.seed_; } /** @@ -137,7 +163,7 @@ public class UpdatableTupleSketch<U, S extends UpdatableSummary<U>> extends Quic */ public void update(final byte[] key, final U value) { if ((key == null) || (key.length == 0)) { return; } - insertOrIgnore(MurmurHash3.hash(key, DEFAULT_UPDATE_SEED)[0] >>> 1, value); + insertOrIgnore(MurmurHash3.hash(key, seed_)[0] >>> 1, value); } /** @@ -149,7 +175,7 @@ public class UpdatableTupleSketch<U, S extends UpdatableSummary<U>> extends Quic */ public void update(final ByteBuffer buffer, final U value) { if (buffer == null || buffer.hasRemaining() == false) { return; } - insertOrIgnore(MurmurHash3.hash(buffer, DEFAULT_UPDATE_SEED)[0] >>> 1, value); + insertOrIgnore(MurmurHash3.hash(buffer, seed_)[0] >>> 1, value); } /** @@ -161,7 +187,7 @@ public class UpdatableTupleSketch<U, S extends UpdatableSummary<U>> extends Quic */ public void update(final int[] key, final U value) { if ((key == null) || (key.length == 0)) { return; } - insertOrIgnore(MurmurHash3.hash(key, DEFAULT_UPDATE_SEED)[0] >>> 1, value); + insertOrIgnore(MurmurHash3.hash(key, seed_)[0] >>> 1, value); } /** @@ -173,7 +199,7 @@ public class UpdatableTupleSketch<U, S extends UpdatableSummary<U>> extends Quic */ public void update(final long[] key, final U value) { if ((key == null) || (key.length == 0)) { return; } - insertOrIgnore(MurmurHash3.hash(key, DEFAULT_UPDATE_SEED)[0] >>> 1, value); + insertOrIgnore(MurmurHash3.hash(key, seed_)[0] >>> 1, value); } void insertOrIgnore(final long hash, final U value) { diff --git a/src/main/java/org/apache/datasketches/tuple/UpdatableTupleSketchBuilder.java b/src/main/java/org/apache/datasketches/tuple/UpdatableTupleSketchBuilder.java index e83862772..63a2f1ec1 100644 --- a/src/main/java/org/apache/datasketches/tuple/UpdatableTupleSketchBuilder.java +++ b/src/main/java/org/apache/datasketches/tuple/UpdatableTupleSketchBuilder.java @@ -19,6 +19,8 @@ package org.apache.datasketches.tuple; +import static org.apache.datasketches.common.Util.DEFAULT_UPDATE_SEED; + import org.apache.datasketches.common.ResizeFactor; import org.apache.datasketches.common.SketchesArgumentException; import org.apache.datasketches.thetacommon.ThetaUtil; @@ -33,6 +35,7 @@ public class UpdatableTupleSketchBuilder<U, S extends UpdatableSummary<U>> { private int nomEntries_; private ResizeFactor resizeFactor_; private float samplingProbability_; + private long seed_; private final SummaryFactory<S> summaryFactory_; private static final float DEFAULT_SAMPLING_PROBABILITY = 1; @@ -46,6 +49,7 @@ public class UpdatableTupleSketchBuilder<U, S extends UpdatableSummary<U>> { nomEntries_ = ThetaUtil.DEFAULT_NOMINAL_ENTRIES; resizeFactor_ = DEFAULT_RESIZE_FACTOR; samplingProbability_ = DEFAULT_SAMPLING_PROBABILITY; + seed_ = DEFAULT_UPDATE_SEED; summaryFactory_ = summaryFactory; } @@ -86,22 +90,34 @@ public class UpdatableTupleSketchBuilder<U, S extends UpdatableSummary<U>> { return this; } + /** + * This is to set the update seed. + * Default seed is the library default update seed. + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + * @return this UpdatableTupleSketchBuilder + */ + public UpdatableTupleSketchBuilder<U, S> setSeed(final long seed) { + seed_ = seed; + return this; + } + /** * Returns an UpdatableTupleSketch with the current configuration of this Builder. * @return an UpdatableTupleSketch */ public UpdatableTupleSketch<U, S> build() { return new UpdatableTupleSketch<>(nomEntries_, resizeFactor_.lg(), samplingProbability_, - summaryFactory_); + summaryFactory_, seed_); } /** - * Resets the Nominal Entries, Resize Factor and Sampling Probability to their default values. + * Resets the Nominal Entries, Resize Factor, Sampling Probability and Seed to their default values. * The assignment of <i>U</i> and <i>S</i> remain the same. */ public void reset() { nomEntries_ = ThetaUtil.DEFAULT_NOMINAL_ENTRIES; resizeFactor_ = DEFAULT_RESIZE_FACTOR; samplingProbability_ = DEFAULT_SAMPLING_PROBABILITY; + seed_ = DEFAULT_UPDATE_SEED; } } diff --git a/src/main/java/org/apache/datasketches/tuple/Util.java b/src/main/java/org/apache/datasketches/tuple/Util.java index a50490320..6051c9431 100644 --- a/src/main/java/org/apache/datasketches/tuple/Util.java +++ b/src/main/java/org/apache/datasketches/tuple/Util.java @@ -37,7 +37,7 @@ 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); + static final short DEFAULT_SEED_HASH = computeSeedHash(DEFAULT_UPDATE_SEED); /** * No argument constructor. @@ -45,14 +45,27 @@ public final class Util { 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. + * Checks that the given ThetaSketch was created with the seed that has the given seed hash. + * Null and empty sketches are not checked. * @param thetaSketch the given ThetaSketch + * @param seedHash the expected seed hash * @throws org.apache.datasketches.common.SketchesArgumentException if the seed hashes do not match */ - static void checkThetaSeedHash(final ThetaSketch thetaSketch) { + static void checkThetaSeedHash(final ThetaSketch thetaSketch, final short seedHash) { if (thetaSketch == null || thetaSketch.isEmpty()) { return; } - checkSeedHashes(DEFAULT_SEED_HASH, thetaSketch.getSeedHash()); + checkSeedHashes(seedHash, thetaSketch.getSeedHash()); + } + + /** + * Checks that the given TupleSketch was created with the seed that has the given seed hash. + * Null and empty sketches are not checked. + * @param tupleSketch the given TupleSketch + * @param seedHash the expected seed hash + * @throws org.apache.datasketches.common.SketchesArgumentException if the seed hashes do not match + */ + static void checkTupleSeedHash(final TupleSketch<?> tupleSketch, final short seedHash) { + if (tupleSketch == null || tupleSketch.isEmpty()) { return; } + checkSeedHashes(seedHash, tupleSketch.getSeedHash()); } /** diff --git a/src/main/java/org/apache/datasketches/tuple/adouble/DoubleTupleSketch.java b/src/main/java/org/apache/datasketches/tuple/adouble/DoubleTupleSketch.java index c5cffd744..2337a535d 100644 --- a/src/main/java/org/apache/datasketches/tuple/adouble/DoubleTupleSketch.java +++ b/src/main/java/org/apache/datasketches/tuple/adouble/DoubleTupleSketch.java @@ -59,6 +59,26 @@ public class DoubleTupleSketch extends UpdatableTupleSketch<Double, DoubleSummar super(1 << lgK, lgResizeFactor, samplingProbability, new DoubleSummaryFactory(mode)); } + /** + * Creates this sketch with the following parameters and the given update seed: + * @param lgK Log_base2 of <i>Nominal Entries</i>. + * @param lgResizeFactor log2(resizeFactor) - value from 0 to 3: + * <pre> + * 0 - no resizing (max size allocated), + * 1 - double internal hash table each time it reaches a threshold + * 2 - grow four times + * 3 - grow eight times (default) + * </pre> + * @param samplingProbability + * <a href="{@docRoot}/resources/dictionary.html#p">See Sampling Probability</a> + * @param mode The DoubleSummary mode to be used + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + */ + public DoubleTupleSketch(final int lgK, final int lgResizeFactor, final float samplingProbability, + final DoubleSummary.Mode mode, final long seed) { + super(1 << lgK, lgResizeFactor, samplingProbability, new DoubleSummaryFactory(mode), seed); + } + /** * Constructs this sketch from a MemorySegment image, which must be from an DoubleTupleSketch, and * usually with data. diff --git a/src/main/java/org/apache/datasketches/tuple/aninteger/IntegerTupleSketch.java b/src/main/java/org/apache/datasketches/tuple/aninteger/IntegerTupleSketch.java index c261b7c31..d3268eb64 100644 --- a/src/main/java/org/apache/datasketches/tuple/aninteger/IntegerTupleSketch.java +++ b/src/main/java/org/apache/datasketches/tuple/aninteger/IntegerTupleSketch.java @@ -59,6 +59,26 @@ public class IntegerTupleSketch extends UpdatableTupleSketch<Integer, IntegerSum super(1 << lgK, lgResizeFactor, samplingProbability, new IntegerSummaryFactory(mode)); } + /** + * Creates this sketch with the following parameters and the given update seed: + * @param lgK Log_base2 of <i>Nominal Entries</i>. + * @param lgResizeFactor log2(resizeFactor) - value from 0 to 3: + * <pre> + * 0 - no resizing (max size allocated), + * 1 - double internal hash table each time it reaches a threshold + * 2 - grow four times + * 3 - grow eight times (default) + * </pre> + * @param samplingProbability + * <a href="{@docRoot}/resources/dictionary.html#p">See Sampling Probability</a> + * @param mode The IntegerSummary mode to be used + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + */ + public IntegerTupleSketch(final int lgK, final int lgResizeFactor, final float samplingProbability, + final IntegerSummary.Mode mode, final long seed) { + super(1 << lgK, lgResizeFactor, samplingProbability, new IntegerSummaryFactory(mode), seed); + } + /** * Constructs this sketch from a MemorySegment image, which must be from an IntegerTupleSketch, and * usually with data. diff --git a/src/main/java/org/apache/datasketches/tuple/strings/ArrayOfStringsTupleSketch.java b/src/main/java/org/apache/datasketches/tuple/strings/ArrayOfStringsTupleSketch.java index 6260f0df2..7032b4e65 100644 --- a/src/main/java/org/apache/datasketches/tuple/strings/ArrayOfStringsTupleSketch.java +++ b/src/main/java/org/apache/datasketches/tuple/strings/ArrayOfStringsTupleSketch.java @@ -62,6 +62,20 @@ public class ArrayOfStringsTupleSketch extends UpdatableTupleSketch<String[], Ar super(1 << lgK, rf.lg(), p, new ArrayOfStringsSummaryFactory()); } + /** + * Constructs new sketch with given ResizeFactor, <i>p</i>, <i>lgK</i> and update seed. + * @param lgK Log_base2 of <i>Nominal Entries</i>. + * <a href="{@docRoot}/resources/dictionary.html#nomEntries">See Nominal Entries</a> + * @param rf ResizeFactor + * <a href="{@docRoot}/resources/dictionary.html#resizeFactor">See Resize Factor</a> + * @param p sampling probability + * <a href="{@docRoot}/resources/dictionary.html#p">See Sampling Probability</a> + * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a> + */ + public ArrayOfStringsTupleSketch(final int lgK, final ResizeFactor rf, final float p, final long seed) { + super(1 << lgK, rf.lg(), p, new ArrayOfStringsSummaryFactory(), seed); + } + /** * Constructs this sketch from a MemorySegment image, which must be from an ArrayOfStringsTupleSketch, and * usually with data. diff --git a/src/test/java/org/apache/datasketches/tuple/CompactSketchWithDoubleSummaryTest.java b/src/test/java/org/apache/datasketches/tuple/CompactSketchWithDoubleSummaryTest.java index a9bb78128..5e9aaa911 100644 --- a/src/test/java/org/apache/datasketches/tuple/CompactSketchWithDoubleSummaryTest.java +++ b/src/test/java/org/apache/datasketches/tuple/CompactSketchWithDoubleSummaryTest.java @@ -35,7 +35,7 @@ public class CompactSketchWithDoubleSummaryTest { @Test public void emptyFromNonPublicConstructorNullArray() { CompactTupleSketch<DoubleSummary> sketch = - new CompactTupleSketch<>(null, null, Long.MAX_VALUE, true); + new CompactTupleSketch<>(null, null, Long.MAX_VALUE, true, Util.DEFAULT_SEED_HASH); Assert.assertTrue(sketch.isEmpty()); Assert.assertFalse(sketch.isEstimationMode()); Assert.assertEquals(sketch.getEstimate(), 0.0); @@ -56,7 +56,7 @@ public class CompactSketchWithDoubleSummaryTest { DoubleSummary[] summaries = (DoubleSummary[]) java.lang.reflect.Array.newInstance(DoubleSummary.class, 0); CompactTupleSketch<DoubleSummary> sketch = - new CompactTupleSketch<>(keys, summaries, Long.MAX_VALUE, true); + new CompactTupleSketch<>(keys, summaries, Long.MAX_VALUE, true, Util.DEFAULT_SEED_HASH); Assert.assertTrue(sketch.isEmpty()); Assert.assertFalse(sketch.isEstimationMode()); Assert.assertEquals(sketch.getEstimate(), 0.0); diff --git a/src/test/java/org/apache/datasketches/tuple/TupleCustomSeedTest.java b/src/test/java/org/apache/datasketches/tuple/TupleCustomSeedTest.java new file mode 100644 index 000000000..7b1c39f35 --- /dev/null +++ b/src/test/java/org/apache/datasketches/tuple/TupleCustomSeedTest.java @@ -0,0 +1,243 @@ +/* + * 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.apache.datasketches.common.Util.DEFAULT_UPDATE_SEED; +import static org.apache.datasketches.common.Util.computeSeedHash; +import static org.testng.Assert.assertEquals; +import static org.testng.Assert.assertNotEquals; +import static org.testng.Assert.assertTrue; +import static org.testng.Assert.expectThrows; + +import java.lang.foreign.MemorySegment; + +import org.apache.datasketches.common.ByteArrayUtil; +import org.apache.datasketches.common.ResizeFactor; +import org.apache.datasketches.common.SketchesArgumentException; +import org.apache.datasketches.common.SketchesStateException; +import org.apache.datasketches.fdt.FdtSketch; +import org.apache.datasketches.theta.UpdatableThetaSketch; +import org.apache.datasketches.tuple.adouble.DoubleSummary; +import org.apache.datasketches.tuple.adouble.DoubleSummaryDeserializer; +import org.apache.datasketches.tuple.adouble.DoubleSummaryFactory; +import org.apache.datasketches.tuple.adouble.DoubleSummarySetOperations; +import org.apache.datasketches.tuple.adouble.DoubleTupleSketch; +import org.apache.datasketches.tuple.aninteger.IntegerSummary; +import org.apache.datasketches.tuple.aninteger.IntegerTupleSketch; +import org.apache.datasketches.tuple.strings.ArrayOfStringsTupleSketch; +import org.testng.annotations.Test; + +/** + * Checks TupleSketches and their set operations created with a custom update seed. + */ +@SuppressWarnings("deprecation") +public class TupleCustomSeedTest { + private static final long SEED = 123L; + private static final short SEED_HASH = computeSeedHash(SEED); + private static final short DEFAULT_SEED_HASH = computeSeedHash(DEFAULT_UPDATE_SEED); + private static final int SEED_HASH_SHORT = 6; + + private final DoubleSummaryFactory factory = new DoubleSummaryFactory(DoubleSummary.Mode.Sum); + private final DoubleSummarySetOperations dsso = new DoubleSummarySetOperations(); + private final DoubleSummaryDeserializer deser = new DoubleSummaryDeserializer(); + + private UpdatableTupleSketch<Double, DoubleSummary> tupleSketch(final long seed, final int start, final int n) { + final UpdatableTupleSketch<Double, DoubleSummary> sk = + new UpdatableTupleSketchBuilder<>(factory).setSeed(seed).build(); + for (int i = start; i < (start + n); i++) { sk.update(i, 1.0); } + return sk; + } + + private static UpdatableThetaSketch thetaSketch(final long seed, final int start, final int n) { + final UpdatableThetaSketch sk = UpdatableThetaSketch.builder().setSeed(seed).build(); + for (int i = start; i < (start + n); i++) { sk.update(i); } + return sk; + } + + private static short seedHashOf(final byte[] bytes) { + return ByteArrayUtil.getShortLE(bytes, SEED_HASH_SHORT); + } + + @Test + public void checkSeedHashIsCarried() { + final UpdatableTupleSketch<Double, DoubleSummary> sk = tupleSketch(SEED, 0, 10); + assertEquals(sk.getSeedHash(), SEED_HASH); + assertEquals(sk.copy().getSeedHash(), SEED_HASH); + assertEquals(sk.compact().getSeedHash(), SEED_HASH); + assertEquals(seedHashOf(sk.compact().toByteArray()), SEED_HASH); + assertEquals(tupleSketch(DEFAULT_UPDATE_SEED, 0, 10).getSeedHash(), DEFAULT_SEED_HASH); + } + + @Test + public void checkDefaultSeedHashMatchesCpp() { + final byte[] bytes = tupleSketch(DEFAULT_UPDATE_SEED, 0, 10).compact().toByteArray(); + assertEquals(seedHashOf(bytes), (short) 37836); + } + + @Test + public void checkSeedChangesHashes() { + assertNotEquals(hashOf(tupleSketch(SEED, 0, 1)), hashOf(tupleSketch(DEFAULT_UPDATE_SEED, 0, 1))); + } + + @Test + public void checkHeapifyCompact() { + final UpdatableTupleSketch<Double, DoubleSummary> sk = tupleSketch(SEED, 0, 100); + final MemorySegment seg = MemorySegment.ofArray(sk.compact().toByteArray()); + expectThrows(SketchesArgumentException.class, () -> TupleSketch.heapifySketch(seg, deser)); + final TupleSketch<DoubleSummary> sk2 = TupleSketch.heapifySketch(seg, deser, SEED); + assertEquals(sk2.getEstimate(), sk.getEstimate()); + assertEquals(sk2.getSeedHash(), SEED_HASH); + //default seed image read with a custom seed is rejected + final MemorySegment segDef = MemorySegment.ofArray(tupleSketch(DEFAULT_UPDATE_SEED, 0, 100).compact().toByteArray()); + expectThrows(SketchesArgumentException.class, () -> TupleSketch.heapifySketch(segDef, deser, SEED)); + } + + @Test + public void checkHeapifyEmptyCompact() { + final byte[] bytes = tupleSketch(SEED, 0, 0).compact().toByteArray(); + assertEquals(seedHashOf(bytes), (short) 0); //empty image carries zero, as in theta + final MemorySegment seg = MemorySegment.ofArray(bytes); + assertTrue(TupleSketch.heapifySketch(seg, deser).isEmpty()); + final TupleSketch<DoubleSummary> sk = TupleSketch.heapifySketch(seg, deser, SEED); + assertTrue(sk.isEmpty()); + assertEquals(sk.getSeedHash(), SEED_HASH); + } + + @Test + public void checkUpdatableSerialization() { + final UpdatableTupleSketch<Double, DoubleSummary> sk = tupleSketch(SEED, 0, 10); + expectThrows(SketchesStateException.class, () -> sk.toByteArray()); + //the updatable form has no seed hash, so it is read as the default seed + final byte[] bytes = tupleSketch(DEFAULT_UPDATE_SEED, 0, 10).toByteArray(); + final MemorySegment seg = MemorySegment.ofArray(bytes); + assertEquals(TupleSketch.heapifySketch(seg, deser).getRetainedEntries(), 10); + expectThrows(SketchesArgumentException.class, () -> TupleSketch.heapifySketch(seg, deser, SEED)); + } + + @Test + public void checkUnion() { + final TupleUnion<DoubleSummary> union = new TupleUnion<>(4096, dsso, SEED); + union.union(tupleSketch(SEED, 0, 10)); + union.union(thetaSketch(SEED, 5, 10), factory.newSummary()); + expectThrows(SketchesArgumentException.class, () -> union.union(tupleSketch(DEFAULT_UPDATE_SEED, 0, 10))); + expectThrows(SketchesArgumentException.class, + () -> union.union(thetaSketch(DEFAULT_UPDATE_SEED, 0, 10), factory.newSummary())); + union.union(tupleSketch(DEFAULT_UPDATE_SEED, 0, 0)); //empty is ignored + final CompactTupleSketch<DoubleSummary> result = union.getResult(); + assertEquals(result.getRetainedEntries(), 15); + assertEquals(result.getSeedHash(), SEED_HASH); + //the default union rejects custom seed sketches + final TupleUnion<DoubleSummary> defUnion = new TupleUnion<>(dsso); + expectThrows(SketchesArgumentException.class, () -> defUnion.union(tupleSketch(SEED, 0, 10))); + } + + @Test + public void checkIntersection() { + final TupleIntersection<DoubleSummary> inter = new TupleIntersection<>(dsso, SEED); + inter.intersect(tupleSketch(SEED, 0, 10)); + inter.intersect(thetaSketch(SEED, 5, 10), factory.newSummary()); + expectThrows(SketchesArgumentException.class, () -> inter.intersect(tupleSketch(DEFAULT_UPDATE_SEED, 0, 10))); + final CompactTupleSketch<DoubleSummary> result = inter.getResult(); + assertEquals(result.getRetainedEntries(), 5); + assertEquals(result.getSeedHash(), SEED_HASH); + final TupleIntersection<DoubleSummary> defInter = new TupleIntersection<>(dsso); + expectThrows(SketchesArgumentException.class, () -> defInter.intersect(tupleSketch(SEED, 0, 10))); + } + + @Test + public void checkAnotB() { + final TupleAnotB<DoubleSummary> anotb = new TupleAnotB<>(SEED); + anotb.setA(tupleSketch(SEED, 0, 10)); + anotb.notB(tupleSketch(SEED, 0, 2)); + anotb.notB(thetaSketch(SEED, 2, 2)); + expectThrows(SketchesArgumentException.class, () -> anotb.notB(tupleSketch(DEFAULT_UPDATE_SEED, 0, 10))); + final CompactTupleSketch<DoubleSummary> result = anotb.getResult(true); + assertEquals(result.getRetainedEntries(), 6); + assertEquals(result.getSeedHash(), SEED_HASH); + final TupleAnotB<DoubleSummary> defAnotB = new TupleAnotB<>(); + expectThrows(SketchesArgumentException.class, () -> defAnotB.setA(tupleSketch(SEED, 0, 10))); + } + + @Test + public void checkStatelessAnotB() { + final CompactTupleSketch<DoubleSummary> r1 = + TupleAnotB.aNotB(tupleSketch(SEED, 0, 10), tupleSketch(SEED, 0, 4), SEED); + assertEquals(r1.getRetainedEntries(), 6); + assertEquals(r1.getSeedHash(), SEED_HASH); + final CompactTupleSketch<DoubleSummary> r2 = + TupleAnotB.aNotB(tupleSketch(SEED, 0, 10), thetaSketch(SEED, 0, 4), SEED); + assertEquals(r2.getRetainedEntries(), 6); + assertEquals(r2.getSeedHash(), SEED_HASH); + expectThrows(SketchesArgumentException.class, + () -> TupleAnotB.aNotB(tupleSketch(SEED, 0, 10), tupleSketch(SEED, 0, 4))); + expectThrows(SketchesArgumentException.class, + () -> TupleAnotB.aNotB(tupleSketch(SEED, 0, 10), thetaSketch(DEFAULT_UPDATE_SEED, 0, 4), SEED)); + } + + @Test + public void checkJaccard() { + final double[] j = JaccardSimilarity.jaccard(tupleSketch(SEED, 0, 10), tupleSketch(SEED, 5, 10), dsso, SEED); + assertEquals(j[1], 5.0 / 15.0, 1e-9); + final double[] jt = JaccardSimilarity.jaccard(tupleSketch(SEED, 0, 10), thetaSketch(SEED, 5, 10), + factory.newSummary(), dsso, SEED); + assertEquals(jt[1], 5.0 / 15.0, 1e-9); + assertTrue(JaccardSimilarity.exactlyEqual(tupleSketch(SEED, 0, 10), tupleSketch(SEED, 0, 10), dsso, SEED)); + expectThrows(SketchesArgumentException.class, + () -> JaccardSimilarity.jaccard(tupleSketch(SEED, 0, 10), tupleSketch(SEED, 5, 10), dsso)); + } + + @Test + public void checkFilter() { + final Filter<DoubleSummary> filter = new Filter<>(s -> s.getValue() > 0); + assertEquals(filter.filter(tupleSketch(SEED, 0, 10)).getSeedHash(), SEED_HASH); + } + + @Test + public void checkDerivedSketches() { + final DoubleTupleSketch dsk = new DoubleTupleSketch(12, ResizeFactor.X8.lg(), 1f, DoubleSummary.Mode.Sum, SEED); + dsk.update(1, 1.0); + assertEquals(dsk.compact().getSeedHash(), SEED_HASH); + + final IntegerTupleSketch isk = new IntegerTupleSketch(12, ResizeFactor.X8.lg(), 1f, IntegerSummary.Mode.Sum, SEED); + isk.update(1, 1); + assertEquals(isk.compact().getSeedHash(), SEED_HASH); + + final ArrayOfStringsTupleSketch ask = new ArrayOfStringsTupleSketch(12, ResizeFactor.X8, 1f, SEED); + ask.update(new String[] {"a"}, new String[] {"b"}); + assertEquals(ask.compact().getSeedHash(), SEED_HASH); + assertEquals(ask.copy().compact().getSeedHash(), SEED_HASH); + + final FdtSketch fsk = new FdtSketch(12, SEED); + fsk.update(new String[] {"a", "b"}); + assertEquals(fsk.compact().getSeedHash(), SEED_HASH); + assertEquals(fsk.copy().compact().getSeedHash(), SEED_HASH); + + final ArrayOfStringsTupleSketch askDef = new ArrayOfStringsTupleSketch(); + askDef.update(new String[] {"a"}, new String[] {"b"}); + assertNotEquals(hashOf(ask), hashOf(askDef)); + } + + private static long hashOf(final TupleSketch<?> sk) { + final TupleSketchIterator<?> it = sk.iterator(); + while (it.next()) { return it.getHash(); } + return 0; + } + +} --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
