Apache Release DataSketches-Java 9.1.0 (for Java 25)

Release 9.1.0

This is a minor release, source and binary compatible with 9.0.0, and like 9.0.0 it requires Java 25. It adds a new filter and several new operations, makes deserialization of every sketch family much stricter, and brings the serialized images of several families into byte-for-byte agreement with C++.

Stricter validation of serialized sketches

• All deserializers now validate their input before allocating memory or reading data. They reject malformed or truncated input with a SketchesArgumentException or another Sketches*Exception.
• This covers:
  • Bloom filter, Count-Min and CPC;
  • Frequencies, including binary images and FrequentLongsSketch.getInstance(String);
  • HLL, Items Quantiles and REQ;
  • Theta, and Tuple including ArrayOfDoubles;
  • VarOpt;
  • ArrayOfNumbersSerDe and the string SerDe.
• We recommend that all users upgrade.

New features

Xor filter

• There are new XorFilter and XorFilterBuilder classes in the filters package. An Xor filter is an immutable approximate-membership filter built from a fixed set of items. It stores 8-bit or 16-bit fingerprints and uses about 1.23 times the fingerprint width in bits per item.
• For the same items and seed, its construction and serialized image match datasketches-rust.

Other additions

• Bloom filter: difference (A NOT B) is new, and invert() is deprecated.
• HLL: HllUnion.update(HllUnion) merges a union without first copying it into a sketch.
• CPC: CpcUnion.update(MemorySegment) merges a serialized sketch without heapifying it.
• Theta: UpdatableThetaSketch.compactTrimmed() compacts and reduces to k in one pass.
• Theta JaccardSimilarity has new seed overloads, so sketches built with a custom seed can be compared.
• Tuple: set operations and JaccardSimilarity now accept custom update seeds and check seed hashes, as Theta does.

Bug fixes

HLL

• The deferred KxQ rebuild after a union is now canonical.
• HIP estimates no longer drift after a merge.
• The compact flag is now set for HLL_6 and HLL_8 images.
• Together, these changes make Java and C++ images agree byte for byte.

Theta and Tuple

• Seed hash checks and empty-sketch handling are aligned between Theta and Tuple, and with C++.
• Empty compact images written by any earlier Java or C++ release are accepted.
• Historical C++ single-item images that omit the single-item flag are reported correctly.
• JaccardSimilarity.exactlyEqual no longer throws for small sketches. The Theta and Tuple versions now work the same way.

Tuple sketches: empty compact images carry a zero seed hash, aligned with Theta

• An empty compact ArrayOfDoubles (AoD) tuple sketch, and an empty compact generic tuple sketch, now carry a zero seed hash in the serialized image. The Theta sketch already does this for an empty compact sketch.
• When an empty image is read, its seed-hash bytes are ignored. So empty images written by earlier releases, which filled in those bytes, still load. Union, intersection and A-not-B also skip the seed-hash check for an empty input. Non-empty images are checked as before.
• This aligns Java with C++ and Python, which already write a zero seed hash for an empty compact tuple sketch. Earlier Java releases rejected those images with "Incompatible Seed Hashes".

t-digest

• Rank and quantile queries are fixed: the interpolation weights were swapped, and the tail cases took the wrong branches.
• Merging preserves the stored min and max.
• Extreme means and NaN centroid means are handled correctly.
• Serialized state is validated.
• Images with buffered values, as written by C++, are accepted.
• Centroids are sorted by value, then by weight, so results are deterministic.

Quantiles

• KLL items: the sorted view is no longer corrupted when a query comes before serialization.
• REQ:
  • Negative values are preserved on deserialization.
  • getRSE() is fixed.
  • The sorted view uses a long shift to compute compactor weights, and each compactor's weight is checked against its level.
• Empty sorted views now throw the documented SketchesArgumentException, including from getMinItem() and getMaxItem(). Each sketch's javadoc names the exception it throws when empty.

Frequencies

• A sketch is now empty only when its stream weight is zero. Before, a sketch whose counters had all been purged counted as empty, so it could serialize as empty and lose its stream weight and error offset.

Sampling

• VarOpt validates totalRWeight on heapify and rejects infinite or NaN weights, as C++ does.

Other

• CPC: CpcWrapper no longer throws on empty sketches.
• Bloom filter: a size of zero bits is rejected.
• ArrayOfStringsSummary: fixed issue #699.
• BinomialBoundsN no longer divides by zero.
• Util.numDigits returns the correct count for 0, 1 and 10^18.

Performance

• QuickSelect picks its pivot as the median of three, so ordered input no longer takes quadratic time.
• Theta union no longer copies the gadget's hash table when the table won't be changed.

Compatibility

• No public API was removed. BloomFilter.invert() is deprecated.
• Tuple sketches: nominal entries are now limited to 2^26.
• Release 9.0.0 and earlier check the seed hash of an empty AoD image. They reject an empty compact AoD sketch serialized by this release with "Incompatible Seed Hashes. 0, 93cc". Upgrade the readers before, or together with, the writers. Non-empty AoD images, and all other sketch images written by this release, can be read by 9.0.0.
• The stricter validation rejects images that are internally inconsistent or shorter than their declared contents, even if earlier releases accepted them. Valid images written by any earlier Java or C++ release still load.

Build and project

• The source release zip builds without a .git directory.
• The zip includes a git.properties file whose values match the manifests of the released jars. This ties the source release to the jars on Maven Central.
• Cross-language tests read the CL files from the datasketches-tck repository.
• SECURITY.md is new.

Known issues

• The README's Known Issues section still refers to /tools/FindBugsExcludeFilter.xml, which no longer exists, and its Checkstyle note may be out of date. Both will be corrected in the next release.

Contributors

Contributors to this release:

• @davecromberge
• @Fengzdadi
• @freakyzoidberg
• @jaideeppyne
• @luciakalf
• @MaxFreedomPollard
• @PerumalsamyR
• @proost
• @tisonkun
• @ZENOTME
• @ziyziy89

Thank you!
@leerho