Make the deferred KxQ rebuild canonical, stop HIP drifting after a merge, set the compact flag for HLL_6/HLL_8 Four defects in the HLL union's deferred rebuild and the flags it writes. 1. checkRebuildCurMinNumKxQ stores the true minimum register value and the count at that minimum, while Hll8Array.updateSlotWithKxQ maintains a different representation, the one its own comment describes as "interpret numAtCurMin as num Zeros", decrementing only when oldValue == 0. When the merged array has no zero register the rebuild leaves curMin > 0 and numAtCurMin is never maintained again, so it freezes and drifts away from the registers. Because the rebuild is triggered lazily by accessors this is directly observable: calling getEstimate() changes the bytes a later getResult() produces. At lgMaxK 7, 8 and 9 the peeked and unpeeked images of the same content differ, with the unpeeked one correct. Estimates and bounds are unaffected because both consumers of numAtCurMin branch on curMin == 0. Emit the canonical form instead, so the rebuilt state is indistinguishable from the incrementally maintained state and the timing of the rebuild is not observable. 2. putOutOfOrder(true) zeroes hipAccum, but hipAndKxQIncrementalUpdate adds to it unconditionally, so every coupon applied after a merge keeps accumulating into a field that is dead once out-of-order is set. The value reached is not a function of the content either: while the rebuild flag is pending the increment is computed against the empty-sketch KxQ defaults, giving 131328 or 396579 for the same sketch depending only on whether an estimate was read. This is also what makes a union result's byte image merge-order dependent. Guard the accumulation on the out-of-order flag. 3. HllArray.toCompactByteArray() returned toUpdatableByteArray(), so the compact flag was never set for HLL_6 and HLL_8, while LIST, SET and HLL_4 all set it. The flag means both that the data is compacted where possible and that the image is immutable; the second applies to every target type. Set it for those two types as well, on the heap and direct paths, both of which operate on a copy so a wrapped segment is never modified. 4. The two relative-error constants were computed with Math.log, which is specified only to within 1 ulp and may use a platform intrinsic. Pin them to the literals Double.toString prints for the computed values, so neither implementation computes a shared constant at runtime. This changes serialized bytes: union results carry different curMin, numAtCurMin and hipAccum, and HLL_6 and HLL_8 compact images differ by the flag bit. Reading is unaffected. One behavioural change beyond the bytes: a compact image is treated as immutable, so writableWrap now rejects an HLL_6 or HLL_8 image produced by toCompactByteArray(), where it previously succeeded. Callers needing a writable wrap should use toUpdatableByteArray(). HllSketchTest.checkCompactFlag is updated: all five modes now follow the toByteArray request. Adds HllKxqRebuildTest; four of its five cases fail without this change, the fifth guards the constants against re-rounding. With the companion datasketches-cpp changes, a 1041 record corpus spanning lgK 4..21, all three target types, 17 sizes across LIST/SET/HLL, round trips and 80 union scenarios goes from 428 differing records to 0, comparing every serialized byte, estimate, composite estimate and bound as raw IEEE bits. Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
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.