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
2 files changed
tree: d863f732175de1691edb9f60b2b5e75ed7722c4b
  1. .github/
  2. .mvn/
  3. src/
  4. tools/
  5. .asf.yaml
  6. .gitattributes
  7. .gitignore
  8. LICENSE
  9. NOTICE
  10. pom.xml
  11. README.md
README.md

Maven Central Coverage Status


Apache® DataSketches™ Core Java Library Component

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.

Build & Runtime Dependencies

Installation Directory Path

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

OpenJDK Version 25

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.

Compilation and Test using Maven

This DataSketches component is structured as a Maven project and Maven is the recommended tool for compile and test.

A Toolchain is required

  • You must have a JDK type toolchain defined in location ~/.m2/toolchains.xml that specifies where to find a locally installed OpenJDK-compatible version 25.
  • Your default $JAVA_HOME compiler must be OpenJDK compatible, specified in the toolchain, and may be a version greater than 25. Note that if your $JAVA_HOME is set to a Java version greater than 25, Maven will automatically use the Java 25 version specified in the toolchain instead. The pom.xml specifies any necessary JVM flags, if required, so no further action is needed.
  • Note that the paths specified in the toolchain must be fully qualified direct paths to the OpenJDK version locations. Using environment variables will not work.

To run normal unit tests:

$ mvn clean test

To install jars built from the downloaded source:

$ mvn clean install -DskipTests=true

This will create the following jars:

  • datasketches-java-X.Y.Z.jar The compiled main class files.
  • datasketches-java-X.Y.Z-tests.jar The compiled test class files.
  • datasketches-java-X.Y.Z-sources.jar The main source files.
  • datasketches-java-X.Y.Z-test-sources.jar The test source files
  • datasketches-java-X.Y.Z-javadoc.jar The compressed Javadocs.

Known Issues

SpotBugs

  • Make sure you configure SpotBugs with the /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.

Checkstyle

  • At the time of this writing, Checkstyle had not been upgraded to handle Java 25 features.