leerho opened a new pull request, #763: URL: https://github.com/apache/datasketches-java/pull/763
## What changed Two concrete methods on `UpdatableThetaSketch`: ```java public CompactThetaSketch compactTrimmed() public CompactThetaSketch compactTrimmed(boolean dstOrdered, MemorySegment dstWSeg) ``` They produce a `CompactThetaSketch` reduced to at most the nominal size `k`, without mutating the source sketch. Today the only way to get a `k`-bounded result is `rebuild()` then `compact()`, and `rebuild()` mutates the sketch and rebuilds its hash table. Java counterpart of apache/datasketches-cpp#524, which came out of apache/datasketches-cpp#515 by @stojkomilos — thanks for raising the need there. ## Why a separate method rather than a `trim` flag on `compact()` The C++ side adds an optional `trim` parameter to the existing `compact()`. Java cannot do the same, for two independent reasons: 1. `ThetaSketch.compact(boolean dstOrdered, MemorySegment dstSeg)` is **abstract** with seven overriders, so its signature cannot grow a parameter. 2. Java has no default parameter values. A `compact(boolean, MemorySegment, boolean trim)` overload would only ever be called with `trim = true` — passing `false` is strictly more typing than the existing two-arg call — so the parameter would be dead weight. A named method makes the opt-in explicit at the call site, which is the actual goal. Both methods are concrete on the base class, so **no subclass changes**. ## Why the Alpha family is excluded `compactTrimmed` throws `UnsupportedOperationException` for `Family.ALPHA`. Alpha maintains theta by its own discipline and never needs reducing to `k`; its `rebuild()` only purges dirty values and does not trim. The guard is a **denylist** (`getFamily() == Family.ALPHA`) rather than a QuickSelect allowlist on purpose. Theta's family names are historically fragmented in a way no other sketch's are, so an allowlist risks wrongly rejecting a legitimate member. This also matters for correctness, not just taste: a dirty Alpha sketch keeps non-zero entries at or above theta in its cache, so `getRetainedEntries(true)` undercounts the array's non-zeros and `selectExcludingZeros` would mis-adjust its pivot. ## Implementation The valid entries are gathered into a dense array first — the method must not modify the sketch, and `QuickSelect.select` permutes whatever array it is given — then: ```java thetaLong = select(validArr, 0, n - 1, k); ``` 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 `HeapQuickSelectSketch.quickSelectAndRebuild()`. The two cannot drift apart. Because it never mutates, `compactTrimmed` also works on a **read-only** sketch, where `rebuild()` throws `SketchesReadOnlyException`. ## Why trimming is an explicit opt-in Relative error scales with `1 / sqrt(retained)`, so discarding entries always widens the confidence bounds. Measured on the C++ side at the default `lg_k`, comparing untrimmed against trimmed 2-sigma widths: 1.03x to 1.27x depending on where in the rebuild cycle the sketch is caught, and up to about `sqrt(15/8)` (~37%) worst case for a sketch grown to just under the rebuild threshold. Separately, a sketch in **exact mode** can retain more than `k` entries — nothing has been evicted, so theta is still 1.0. Trimming there discards real data and returns an estimating sketch, so `getEstimate()` carries error where it would have returned an exact count. Both effects are documented on the methods and pinned by tests. ## How tested New `CompactTrimTest`, 6 cases: - the four ordered/trimmed combinations, asserting the trimmed result matches `rebuild()` + `compact()` on theta and retained set, that every retained hash is below the new theta, and that **the source sketch is unmodified** - **serialization equality**: `compactTrimmed(true, null).toByteArray()` is byte-for-byte identical to `rebuild().compact(true, null).toByteArray()`, and the no-arg form matches the explicit one - exact mode converting to estimation, with n still inside the 3-sigma bounds - bounds widening for a source already in estimation mode - empty and below-k sketches, where trimming is a no-op - Alpha rejecting the call while plain `compact()` still works on it ``` mvn test Tests run: 2228, Failures: 0, Errors: 0 BUILD SUCCESS mvn -Pcheck_java_files test Tests run: 73, Failures: 0, Errors: 0 BUILD SUCCESS ``` 🤖 Generated with [Claude Code](https://claude.com/claude-code) https://claude.ai/code/session_017EDHa7UhfW4eSj5L82panJ -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
