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 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_017EDHa7UhfW4eSj5L82panJ
This is the core Java component of the DataSketches library. It contains all of the sketching algorithms and can be accessed directly from user applications.
This component is also a dependency of other components of the library that create adaptors for target systems, such as the Apache Pig adaptor, the Apache Hive adaptor, and others.
Note that we have parallel core library components for C++, Python, GO, and Rust implementations of many of the same sketch algorithms:
Please visit the main DataSketches website for more information.
If you are interested in making contributions to this site, please see our Community page for how to contact us.
NOTE: This component accesses resource files for testing. As a result, the directory elements of the full absolute path of the target installation directory must qualify as Java identifiers. In other words, the directory elements must not have any space characters (or non-Java identifier characters) in any of the path elements. This is required by the Oracle Java Specification in order to ensure location-independent access to resources: See Oracle Location-Independent Access to Resources
At minimum, an OpenJDK-compatible build of Java 25, provided by one of the Open-Source JVM providers, such as Azul Systems, Red Hat, SAP, Eclipse Temurin, etc, is required. All of the testing of this release has been performed with the Eclipse Temurin build.
This DataSketches component is structured as a Maven project and Maven is the recommended tool for compile and test.
$ mvn clean test
$ mvn clean install -DskipTests=true
This will create the following jars:
/tools/FindBugsExcludeFilter.xml file. Otherwise, you may get a lot of false positive or low risk issues that we have examined and eliminated with this exclusion file.