This is an automated email from the ASF dual-hosted git repository. leerho pushed a commit to branch theta-compact-trim in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 63fcb766dcc0030e6659e81a78c8991db7ecb83e Author: Lee Rhodes <[email protected]> AuthorDate: Mon Sep 7 19:35:16 2026 -0700 Add UpdatableThetaSketch.compactTrimmed() to compact and reduce to k in one pass An update sketch retains more than the nominal size k between rebuilds. Callers who need a result bounded by k currently have to call rebuild(), which mutates the sketch and rebuilds its hash table, before compact(). This adds two concrete methods on UpdatableThetaSketch: public CompactThetaSketch compactTrimmed() public CompactThetaSketch compactTrimmed(boolean dstOrdered, MemorySegment dstWSeg) Both are concrete on the base, so none of the subclasses change. A separate method rather than a trim flag on compact(): Java has no default parameter values, so a flag would only ever be passed true, and compact(dstOrdered, MemorySegment) is abstract with seven overriders, so its signature cannot grow a parameter in any case. The implementation gathers the valid entries into a dense array, since the method must not modify the sketch and QuickSelect.select permutes whatever array it is given, then selects 0-based index k. That is the same hash value the (k + 1) 1-based pivot yields in rebuild(), so the two cannot drift apart, and a test asserts the result serializes byte-for-byte identically to rebuild() + compact(). Because it never mutates, this also works on a read-only sketch, where rebuild() throws SketchesReadOnlyException. The Alpha family is excluded and throws UnsupportedOperationException: it maintains theta by its own discipline and never needs reducing to k. The guard is a family denylist rather than a QuickSelect allowlist, because Theta's family names are historically fragmented and an allowlist could wrongly reject a legitimate member. Trimming stays an explicit opt-in because it is lossy. Relative error scales with 1 / sqrt(retained), so discarding entries always widens the confidence bounds, and a sketch in exact mode that retains more than k loses exactness and is returned in estimation mode. Both effects are documented and pinned by tests. This is the Java counterpart of apache/datasketches-cpp#524. Co-Authored-By: Claude Opus 5 <[email protected]> Claude-Session: https://claude.ai/code/session_017EDHa7UhfW4eSj5L82panJ --- .../datasketches/theta/UpdatableThetaSketch.java | 95 ++++++++++ .../apache/datasketches/theta/CompactTrimTest.java | 194 +++++++++++++++++++++ 2 files changed, 289 insertions(+) diff --git a/src/main/java/org/apache/datasketches/theta/UpdatableThetaSketch.java b/src/main/java/org/apache/datasketches/theta/UpdatableThetaSketch.java index 8b75c7883..693fa02db 100644 --- a/src/main/java/org/apache/datasketches/theta/UpdatableThetaSketch.java +++ b/src/main/java/org/apache/datasketches/theta/UpdatableThetaSketch.java @@ -21,6 +21,7 @@ package org.apache.datasketches.theta; import static java.nio.charset.StandardCharsets.UTF_8; import static org.apache.datasketches.common.Util.LONG_MAX_VALUE_AS_DOUBLE; +import static org.apache.datasketches.common.QuickSelect.select; import static org.apache.datasketches.hash.MurmurHash3.hash; import static org.apache.datasketches.theta.CompactOperations.componentsToCompact; import static org.apache.datasketches.theta.PreambleUtil.COMPACT_FLAG_MASK; @@ -169,6 +170,100 @@ public abstract class UpdatableThetaSketch extends ThetaSketch { getCache()); } + /** + * Converts this sketch to an ordered <i>CompactThetaSketch</i> on the Java heap, reduced to no + * more than <i>Nominal Entries</i> (or <i>k</i>) retained entries. + * + * <p>Equivalent to {@link #compactTrimmed(boolean, MemorySegment) compactTrimmed(true, null)}. + * See that method for the accuracy this gives up; trimming is lossy and is never required for + * correctness.</p> + * + * @return this sketch as an ordered <i>CompactThetaSketch</i> of at most <i>k</i> entries. + */ + public CompactThetaSketch compactTrimmed() { + return compactTrimmed(true, null); + } + + /** + * Convert this sketch to a <i>CompactThetaSketch</i> reduced to no more than + * <i>Nominal Entries</i> (or <i>k</i>) retained entries. + * + * <p>If this sketch retains more than <i>k</i> entries, <i>theta</i> is lowered to the + * (<i>k</i> + 1)th smallest retained hash value and only the <i>k</i> values below it are + * kept. Otherwise this is identical to {@link #compact(boolean, MemorySegment)}. + * This sketch is never modified, so unlike {@link #rebuild()} this may also be called on a + * read-only sketch.</p> + * + * <p>This produces the same result as {@link #rebuild()} followed by + * {@link #compact(boolean, MemorySegment)}, without mutating this sketch or rebuilding its + * hash table.</p> + * + * <p>The Alpha family does not support trimming and throws + * <i>UnsupportedOperationException</i>. Alpha maintains theta by its own discipline and never + * needs to be reduced to <i>k</i>. Every other member of this hierarchy is a QuickSelect + * sketch and is supported, including the read-only and concurrent variants.</p> + * + * <p>Trimming is lossy and is never required for correctness. It discards retained entries, + * and because the relative error scales with 1 / sqrt(retained), it always degrades accuracy + * and widens the confidence bounds, whatever mode this sketch is in. Worst case, a sketch + * grown to just under the rebuild threshold loses nearly half its entries. A sketch in exact + * mode that retains more than <i>k</i> entries loses exactness as well: the result is returned + * in estimation mode, so <i>getEstimate()</i> carries error where it would otherwise have + * returned an exact count. Only call this if a bounded result size matters more than that + * accuracy.</p> + * + * @param dstOrdered + * <a href="{@docRoot}/resources/dictionary.html#dstOrdered">See Destination Ordered</a> + * @param dstWSeg + * <a href="{@docRoot}/resources/dictionary.html#dstSeg">See Destination MemorySegment</a>. + * @return this sketch as a <i>CompactThetaSketch</i> of at most <i>k</i> entries. + */ + public CompactThetaSketch compactTrimmed(final boolean dstOrdered, final MemorySegment dstWSeg) { + if (getFamily() == Family.ALPHA) { + throw new UnsupportedOperationException( + "The Alpha family does not support trimming; it maintains theta by its own discipline " + + "and never needs to be reduced to k."); + } + long thetaLong = getThetaLong(); + int curCount = getRetainedEntries(true); + long[] hashArr = getCache(); + + final int k = 1 << getLgNomLongs(); + if (curCount > k) { + //Gather the valid entries, non-zero and below the current theta, into a dense array. + //Copying is required in any case: this method must not modify the sketch, and select() + //permutes whatever array it is given. This mirrors the C++ path, which likewise copies + //the retained entries before selecting. + final long[] validArr = new long[curCount]; + int n = 0; + for (final long hash : hashArr) { + if ((hash != 0L) && (hash < thetaLong) && (n < curCount)) { validArr[n++] = hash; } + } + //select() partitions validArr in place, which is safe: it is our own copy, never the + //sketch's cache. Index k is 0-based, so this is the (k + 1)th smallest hash, the same + //value the (k + 1) 1-based pivot yields in rebuild(). + thetaLong = select(validArr, 0, n - 1, k); + final long[] trimmedArr = new long[k]; + int j = 0; + for (int i = 0; i < n; i++) { + final long hash = validArr[i]; + if ((hash < thetaLong) && (j < k)) { trimmedArr[j++] = hash; } + } + hashArr = (j == k) ? trimmedArr : java.util.Arrays.copyOf(trimmedArr, j); + curCount = j; + } + return componentsToCompact( + thetaLong, + curCount, + getSeedHash(), + isEmpty(), + false, //is src compact + false, //is src ordered + dstOrdered, + dstWSeg, + hashArr); + } + @Override public int getCompactBytes() { final int preLongs = getCompactPreambleLongs(); diff --git a/src/test/java/org/apache/datasketches/theta/CompactTrimTest.java b/src/test/java/org/apache/datasketches/theta/CompactTrimTest.java new file mode 100644 index 000000000..6e9cfac3d --- /dev/null +++ b/src/test/java/org/apache/datasketches/theta/CompactTrimTest.java @@ -0,0 +1,194 @@ +/* + * 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.theta; + +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 java.util.Arrays; + +import org.apache.datasketches.common.Family; +import org.testng.annotations.Test; + +/** + * Tests the optional trim flag on UpdatableThetaSketch.compact(). + */ +public class CompactTrimTest { + private static final int K = 4096; //default nominal entries + + private static UpdatableThetaSketch sketchOf(final int n) { + final UpdatableThetaSketch sk = UpdatableThetaSketch.builder().setNominalEntries(K).build(); + for (int i = 0; i < n; i++) { sk.update(i); } + return sk; + } + + private static long[] hashesOf(final CompactThetaSketch sk) { + final long[] arr = new long[sk.getRetainedEntries(true)]; + final HashIterator it = sk.iterator(); + int i = 0; + while (it.next()) { arr[i++] = it.get(); } + Arrays.sort(arr); + return arr; + } + + @Test + public void allFourOrderedTrimCases() { + final UpdatableThetaSketch sk = sketchOf(8000); + assertTrue(sk.getRetainedEntries(true) > K); //over-provisioned before trimming + final int retainedBefore = sk.getRetainedEntries(true); + final long thetaBefore = sk.getThetaLong(); + + //the trimmed result is what rebuild() + compact() would produce + final UpdatableThetaSketch copy = UpdatableThetaSketch.heapify( + java.lang.foreign.MemorySegment.ofArray(sk.toByteArray())); + final CompactThetaSketch expected = copy.rebuild().compact(true, null); + final long[] expectedHashes = hashesOf(expected); + + //case 1: ordered, not trimmed (the default) keeps every retained entry + final CompactThetaSketch c1 = sk.compact(true, null); + assertTrue(c1.isOrdered()); + assertEquals(c1.getRetainedEntries(true), retainedBefore); + assertEquals(c1.getThetaLong(), thetaBefore); + + //case 2: unordered, not trimmed + final CompactThetaSketch c2 = sk.compact(false, null); + assertEquals(c2.getRetainedEntries(true), retainedBefore); + assertEquals(c2.getThetaLong(), thetaBefore); + + //case 3: ordered and trimmed + final CompactThetaSketch c3 = sk.compactTrimmed(true, null); + assertTrue(c3.isOrdered()); + assertEquals(c3.getRetainedEntries(true), K); + assertTrue(c3.getThetaLong() < thetaBefore); //new theta is the (k+1)th smallest hash + assertEquals(c3.getThetaLong(), expected.getThetaLong()); + assertEquals(hashesOf(c3), expectedHashes); + for (final long h : hashesOf(c3)) { assertTrue(h < c3.getThetaLong()); } + + //case 4: unordered and trimmed: same set and theta + final CompactThetaSketch c4 = sk.compactTrimmed(false, null); + assertEquals(c4.getRetainedEntries(true), K); + assertEquals(c4.getThetaLong(), expected.getThetaLong()); + assertEquals(hashesOf(c4), expectedHashes); + + //the source sketch must be untouched by any of the four + assertEquals(sk.getRetainedEntries(true), retainedBefore); + assertEquals(sk.getThetaLong(), thetaBefore); + } + + @Test + public void trimConvertsExactModeToEstimation() { + //an update sketch can retain more than k entries while still in exact mode: + //nothing has been evicted yet, so theta is still 1.0 and the count is exact + final int n = 5000; + final UpdatableThetaSketch sk = sketchOf(n); + assertTrue(sk.getRetainedEntries(true) > K); + assertFalse(sk.isEstimationMode()); + assertEquals(sk.getTheta(), 1.0); + + //not trimming keeps every entry and the exact count + final CompactThetaSketch exact = sk.compact(true, null); + assertFalse(exact.isEstimationMode()); + assertEquals(exact.getRetainedEntries(true), n); + assertEquals(exact.getEstimate(), (double)n); + + //trimming is lossy: it discards real data, lowers theta below 1.0 and the + //result is an estimate carrying error where the source held an exact count + final CompactThetaSketch trimmed = sk.compactTrimmed(true, null); + assertTrue(trimmed.isEstimationMode()); + assertEquals(trimmed.getRetainedEntries(true), K); + assertTrue(trimmed.getTheta() < 1.0); + assertTrue(trimmed.getEstimate() != (double)n); + //the estimate is still sound: n must lie inside the 3-sigma bounds + assertTrue(trimmed.getLowerBound(3) <= n); + assertTrue(trimmed.getUpperBound(3) >= n); + } + + @Test + public void trimWidensBoundsInEstimationMode() { + //trimming is lossy even when the source is already estimating: it discards + //retained entries, and the relative error scales with 1 / sqrt(retained) + final UpdatableThetaSketch sk = sketchOf(40000); + assertTrue(sk.isEstimationMode()); + assertTrue(sk.getRetainedEntries(true) > K); + + final CompactThetaSketch plain = sk.compact(true, null); + final CompactThetaSketch trimmed = sk.compactTrimmed(true, null); + assertEquals(trimmed.getRetainedEntries(true), K); + assertTrue(plain.getRetainedEntries(true) > trimmed.getRetainedEntries(true)); + + //fewer retained entries -> strictly wider confidence interval + final double plainWidth = plain.getUpperBound(2) - plain.getLowerBound(2); + final double trimmedWidth = trimmed.getUpperBound(2) - trimmed.getLowerBound(2); + assertTrue(trimmedWidth > plainWidth); + } + + @Test + public void trimOnEmptyAndBelowK() { + //empty: trimming changes nothing + final UpdatableThetaSketch empty = sketchOf(0); + final CompactThetaSketch emptyResult = empty.compactTrimmed(true, null); + assertTrue(emptyResult.isEmpty()); + assertEquals(emptyResult.getRetainedEntries(true), 0); + + //below k: nothing to trim, theta and entries are preserved + final UpdatableThetaSketch small = sketchOf(100); + assertFalse(small.isEstimationMode()); + final CompactThetaSketch smallResult = small.compactTrimmed(true, null); + assertFalse(smallResult.isEstimationMode()); + assertEquals(smallResult.getRetainedEntries(true), 100); + assertEquals(smallResult.getThetaLong(), small.getThetaLong()); + assertEquals(smallResult.getEstimate(), 100.0); + } + + @Test + public void serializesIdenticallyToRebuildThenCompact() { + //binary compatibility is the first priority: the trimmed result must serialize to exactly + //the same bytes as the rebuild() + compact() path it replaces + final UpdatableThetaSketch sk = sketchOf(8000); + assertTrue(sk.getRetainedEntries(true) > K); + + final UpdatableThetaSketch copy = UpdatableThetaSketch.heapify( + java.lang.foreign.MemorySegment.ofArray(sk.toByteArray())); + final byte[] viaRebuild = copy.rebuild().compact(true, null).toByteArray(); + final byte[] viaTrim = sk.compactTrimmed(true, null).toByteArray(); + assertEquals(viaTrim, viaRebuild); + + //the no-arg convenience must match the explicit ordered/heap form + assertEquals(sk.compactTrimmed().toByteArray(), viaTrim); + } + + @Test + public void alphaDoesNotSupportTrimming() { + //Alpha maintains theta by its own discipline and never needs reducing to k + final UpdatableThetaSketch alpha = UpdatableThetaSketch.builder() + .setFamily(Family.ALPHA).setNominalEntries(512).build(); + for (int i = 0; i < 8000; i++) { alpha.update(i); } + //plain compact still works + final CompactThetaSketch plain = alpha.compact(true, null); + assertTrue(plain.getRetainedEntries(true) > 0); + try { + alpha.compactTrimmed(true, null); + fail("Alpha must reject trimming"); + } catch (final UnsupportedOperationException expected) { } + } + +} --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
