This is an automated email from the ASF dual-hosted git repository.

leerho pushed a commit to branch count-min-v2
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git

commit 1963d150adbc906ad246f37cc2764965220414db
Author: Lee Rhodes <[email protected]>
AuthorDate: Tue Nov 10 16:45:34 2026 -0800

    Count-Min: write serialization version 2, keep reading version 1
    
    New sketches use the cross-language Count-Min format, version 2, defined
    in the TCK (docs/count-min-format.md):
    - row seeds: rowSeed[i] = XXH64(LE64(i), seed)
    - items hashed with XxHash64: longs as 8 little-endian bytes, strings as
      UTF-8, byte arrays as given
    - bucket = (hash >>> 1) % numBuckets
    - serial version byte 2; the byte layout is unchanged
    
    A sketch read from a version 1 image keeps the version 1 hashing
    (Random seeds, MurmurHash3, floorMod) and is written back as version 1.
    Merging version 1 with version 2 throws, and other serial versions are
    rejected. A null byte array is now ignored, like an empty one.
    
    Tests check every test vector in the spec (XXH64, row seeds, buckets and
    both images), and the version 1 path against an independent computation
    of the legacy hashing.
    
    Co-Authored-By: Claude Opus 5.5 <[email protected]>
---
 .../apache/datasketches/count/CountMinSketch.java  | 112 +++++++++---
 .../datasketches/count/CountMinSketchTest.java     | 187 +++++++++++++++++++++
 2 files changed, 277 insertions(+), 22 deletions(-)

diff --git a/src/main/java/org/apache/datasketches/count/CountMinSketch.java 
b/src/main/java/org/apache/datasketches/count/CountMinSketch.java
index 5354eb702..f5840673e 100644
--- a/src/main/java/org/apache/datasketches/count/CountMinSketch.java
+++ b/src/main/java/org/apache/datasketches/count/CountMinSketch.java
@@ -21,6 +21,8 @@ package org.apache.datasketches.count;
 
 import static java.lang.foreign.ValueLayout.JAVA_BYTE;
 import static java.lang.foreign.ValueLayout.JAVA_LONG_UNALIGNED;
+import static org.apache.datasketches.hash.XxHash64.hash;
+import static org.apache.datasketches.hash.XxHash64.hashBytes;
 
 import java.lang.foreign.MemorySegment;
 import java.nio.charset.StandardCharsets;
@@ -42,8 +44,19 @@ import org.apache.datasketches.hash.MurmurHash3;
  * providing approximate counts with configurable error bounds.
  *
  * Reference: http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf
+ *
+ * <p>New sketches are written in serialization version 2, the cross-language 
format defined in
+ * <a 
href="https://github.com/apache/datasketches-tck/blob/main/docs/count-min-format.md";>
+ * the DataSketches TCK</a>. Version 2 hashes items with XxHash64, so its 
images give the same results
+ * in every language. A sketch read from a version 1 image keeps the version 1 
hashing, which used
+ * MurmurHash3 and seeds from {@link Random}, and is written back as version 1.
+ * Version 1 and version 2 sketches can't be merged.</p>
  */
 public class CountMinSketch {
+  static final byte SERIAL_VERSION_1 = 1;
+  static final byte SERIAL_VERSION_2 = 2;
+
+  private final byte serialVersion_;
   private final byte numHashes_;
   private final int numBuckets_;
   private final long seed_;
@@ -65,13 +78,25 @@ public class CountMinSketch {
 
   /**
    * Creates a CountMin sketch with given number of hash functions and buckets,
-   * and a user-specified seed.
+   * and a user-specified seed. The sketch uses serialization version 2.
    *
    * @param numHashes The number of hash functions to apply to items
    * @param numBuckets Array size for each of the hashing function
    * @param seed The base hash seed
    */
   CountMinSketch(final byte numHashes, final int numBuckets, final long seed) {
+    this(numHashes, numBuckets, seed, SERIAL_VERSION_2);
+  }
+
+  /**
+   * Creates a CountMin sketch that hashes items as the given serialization 
version does.
+   *
+   * @param numHashes The number of hash functions to apply to items
+   * @param numBuckets Array size for each of the hashing function
+   * @param seed The base hash seed
+   * @param serialVersion 1 for the legacy hashing, 2 for the cross-language 
hashing
+   */
+  private CountMinSketch(final byte numHashes, final int numBuckets, final 
long seed, final byte serialVersion) {
     // Validate numHashes
     if (numHashes <= 0) {
       throw new SketchesArgumentException("Number of hash functions must be 
positive, got: " + numHashes);
@@ -102,6 +127,7 @@ public class CountMinSketch {
           + "Consider reducing numHashes or numBuckets.");
     }
 
+    serialVersion_ = serialVersion;
     numHashes_ = numHashes;
     numBuckets_ = numBuckets;
     seed_ = seed;
@@ -109,9 +135,16 @@ public class CountMinSketch {
     sketchArray_ = new long[(int) totalSize];
     totalWeight_ = 0;
 
-    final Random rand = new Random(seed);
-    for (int i = 0; i < numHashes; i++) {
-      hashSeeds_[i] = rand.nextLong();
+    if (serialVersion == SERIAL_VERSION_1) {
+      final Random rand = new Random(seed);
+      for (int i = 0; i < numHashes; i++) {
+        hashSeeds_[i] = rand.nextLong();
+      }
+    } else {
+      // rowSeed[i] = XXH64(LE64(i), seed): XxHash64.hash(long, seed) hashes 
the 8 little-endian bytes of i
+      for (int i = 0; i < numHashes; i++) {
+        hashSeeds_[i] = hash(i, seed);
+      }
     }
   }
 
@@ -128,13 +161,42 @@ public class CountMinSketch {
     final long[] updateLocations = new long[numHashes_];
 
     for (int i = 0; i < numHashes_; i++) {
-      final long[] index = MurmurHash3.hash(item, hashSeeds_[i]);
-      updateLocations[i] = (i * (long)numBuckets_) + Math.floorMod(index[0], 
numBuckets_);
+      updateLocations[i] = (i * (long) numBuckets_) + bucket(item, 
hashSeeds_[i]);
     }
 
     return updateLocations;
   }
 
+  private long[] getHashes(final long item) {
+    if (serialVersion_ == SERIAL_VERSION_1) {
+      return getHashes(longToBytes(item));
+    }
+    final long[] updateLocations = new long[numHashes_];
+    for (int i = 0; i < numHashes_; i++) {
+      // XxHash64.hash(long, seed) hashes the 8 little-endian bytes of the 
item, as version 2 requires
+      final long h = hash(item, hashSeeds_[i]);
+      updateLocations[i] = (i * (long) numBuckets_) + ((h >>> 1) % 
numBuckets_);
+    }
+    return updateLocations;
+  }
+
+  private long bucket(final byte[] item, final long rowSeed) {
+    if (serialVersion_ == SERIAL_VERSION_1) {
+      return Math.floorMod(MurmurHash3.hash(item, rowSeed)[0], numBuckets_);
+    }
+    final long h = hashBytes(item, 0, item.length, rowSeed);
+    return (h >>> 1) % numBuckets_;
+  }
+
+  /**
+   * Returns the serialization version this sketch hashes and serializes with:
+   * 2 for new sketches, or 1 for a sketch read from a version 1 image.
+   * @return the serialization version
+   */
+  byte getSerialVersion() {
+    return serialVersion_;
+  }
+
   /**
    * Checks if the CountMinSketch has processed any items.
    * @return True if the sketch is empty, otherwise false.
@@ -214,7 +276,7 @@ public class CountMinSketch {
    * @param weight The weight of the item.
    */
   public void update(final long item, final long weight) {
-    update(longToBytes(item), weight);
+    updateLocations(getHashes(item), weight);
   }
 
   /**
@@ -236,12 +298,14 @@ public class CountMinSketch {
    * @param weight The weight of the item.
    */
   public void update(final byte[] item, final long weight) {
-    if (item.length == 0) {
+    if ((item == null) || (item.length == 0)) {
       return;
     }
+    updateLocations(getHashes(item), weight);
+  }
 
+  private void updateLocations(final long[] hashLocations, final long weight) {
     totalWeight_ += weight > 0 ? weight : -weight;
-    final long[] hashLocations = getHashes(item);
     for (final long h : hashLocations) {
       sketchArray_[(int) h] += weight;
     }
@@ -253,7 +317,7 @@ public class CountMinSketch {
    * @return Estimated frequency.
    */
   public long getEstimate(final long item) {
-    return getEstimate(longToBytes(item));
+    return estimateAt(getHashes(item));
   }
 
   /**
@@ -276,11 +340,13 @@ public class CountMinSketch {
    * @return Estimated frequency.
    */
   public long getEstimate(final byte[] item) {
-    if (item.length == 0) {
+    if ((item == null) || (item.length == 0)) {
       return 0;
     }
+    return estimateAt(getHashes(item));
+  }
 
-    final long[] hashLocations = getHashes(item);
+  private long estimateAt(final long[] hashLocations) {
     long res = sketchArray_[(int) hashLocations[0]];
     // Start from index 1 to avoid processing first element twice
     for (int i = 1; i < hashLocations.length; i++) {
@@ -296,7 +362,7 @@ public class CountMinSketch {
    * @return Upper bound of estimated frequency.
    */
   public long getUpperBound(final long item) {
-    return getUpperBound(longToBytes(item));
+    return getEstimate(item) + (long) (getRelativeError() * getTotalWeight_());
   }
 
   /**
@@ -319,7 +385,7 @@ public class CountMinSketch {
    * @return Upper bound of estimated frequency.
    */
   public long getUpperBound(final byte[] item) {
-    if (item.length == 0) {
+    if ((item == null) || (item.length == 0)) {
       return 0;
     }
 
@@ -332,7 +398,7 @@ public class CountMinSketch {
    * @return Lower bound of estimated frequency.
    */
   public long getLowerBound(final long item) {
-    return getLowerBound(longToBytes(item));
+    return getEstimate(item);
   }
 
   /**
@@ -373,6 +439,10 @@ public class CountMinSketch {
     if (!acceptableConfig) {
       throw new SketchesException("Incompatible sketch configuration.");
     }
+    if (serialVersion_ != other.serialVersion_) {
+      throw new SketchesException("Cannot merge sketches with different 
serialization versions: "
+          + serialVersion_ + " and " + other.serialVersion_);
+    }
 
     for (int i = 0; i < sketchArray_.length; i++) {
       sketchArray_[i] += other.sketchArray_[i];
@@ -404,8 +474,7 @@ public class CountMinSketch {
     // Long 0
     final int preambleLongs = Family.COUNTMIN.getMinPreLongs();
     posSeg.setByte((byte) preambleLongs);
-    final int serialVersion = 1;
-    posSeg.setByte((byte) serialVersion);
+    posSeg.setByte(serialVersion_);
     final int familyId = Family.COUNTMIN.getID();
     posSeg.setByte((byte) familyId);
     final int flagsByte = isEmpty() ? Flag.IS_EMPTY.mask() : 0;
@@ -457,10 +526,9 @@ public class CountMinSketch {
       throw new SketchesArgumentException("Preamble longs mismatch: expected " 
+ expectedPreambleLongs
           + ", actual " + preambleLongs);
     }
-    final int expectedSerialVersion = 1;
-    if (serialVersion != expectedSerialVersion) {
-      throw new SketchesArgumentException("Serial version mismatch: expected " 
+ expectedSerialVersion
-          + ", actual " + serialVersion);
+    if ((serialVersion != SERIAL_VERSION_1) && (serialVersion != 
SERIAL_VERSION_2)) {
+      throw new SketchesArgumentException("Serial version mismatch: expected " 
+ SERIAL_VERSION_1
+          + " or " + SERIAL_VERSION_2 + ", actual " + serialVersion);
     }
     final int expectedFamilyId = Family.COUNTMIN.getID();
     if (familyId != expectedFamilyId) {
@@ -483,7 +551,7 @@ public class CountMinSketch {
       final long arrayBytes = (long) numHashes * numBuckets * Long.BYTES;
       Util.checkBounds(preambleBytes, Long.BYTES + Math.max(arrayBytes, 0), 
b.length);
     }
-    final CountMinSketch cms = new CountMinSketch(numHashes, numBuckets, seed);
+    final CountMinSketch cms = new CountMinSketch(numHashes, numBuckets, seed, 
serialVersion);
     if (empty) {
       return cms;
     }
diff --git 
a/src/test/java/org/apache/datasketches/count/CountMinSketchTest.java 
b/src/test/java/org/apache/datasketches/count/CountMinSketchTest.java
index 59590d9a6..e5adb8ddd 100644
--- a/src/test/java/org/apache/datasketches/count/CountMinSketchTest.java
+++ b/src/test/java/org/apache/datasketches/count/CountMinSketchTest.java
@@ -24,10 +24,16 @@ import static org.testng.Assert.assertFalse;
 import static org.testng.Assert.assertThrows;
 import static org.testng.Assert.assertTrue;
 
+import java.nio.charset.StandardCharsets;
+import java.util.HexFormat;
+import java.util.Random;
+
 import org.apache.datasketches.common.AllocationTracker;
 import org.apache.datasketches.common.ByteArrayUtil;
 import org.apache.datasketches.common.SketchesArgumentException;
 import org.apache.datasketches.common.SketchesException;
+import org.apache.datasketches.hash.MurmurHash3;
+import org.apache.datasketches.hash.XxHash64;
 import org.testng.annotations.Test;
 
 public class CountMinSketchTest {
@@ -271,4 +277,185 @@ public class CountMinSketchTest {
     assertThrows(SketchesArgumentException.class, () -> 
CountMinSketch.deserialize(shortBytes, seed));
   }
 
+  // ---- Serialization version 2: test vectors from the TCK spec 
docs/count-min-format.md, section 7 ----
+
+  private static final long SPEC_SEED = 9001L;
+
+  // 7.1 XXH64 and 7.2 row seeds
+  @Test
+  public void v2XxHashAndRowSeedVectors() {
+    final byte[] empty = new byte[0];
+    assertEquals(XxHash64.hashBytes(empty, 0, 0, 0), 0xEF46DB3751D8E999L);
+    assertEquals(XxHash64.hashBytes(utf8("a"), 0, 1, 0), 0xD24EC4F1A98C6E5BL);
+    assertEquals(XxHash64.hashBytes(utf8("abc"), 0, 3, 0), 
0x44BC2CF5AD770999L);
+
+    final long[] seeds9001 = { 0xD71D64972584A288L, 0xEFE8454A6499F311L, 
0x23819BE21B1B1D9EL };
+    final long[] seeds42 = { 0xB71B47EBDA15746CL, 0x9ED50FD59358D232L, 
0xD19FE30002B9A3CDL };
+    for (int i = 0; i < 3; i++) {
+      assertEquals(XxHash64.hash(i, 9001L), seeds9001[i]);
+      assertEquals(XxHash64.hash(i, 42L), seeds42[i]);
+    }
+  }
+
+  // 7.3 item buckets, observed through the counters a single update sets
+  @Test
+  public void v2BucketVectors() {
+    assertBuckets(SPEC_SEED, 1L, 185, 898, 4);
+    assertBuckets(SPEC_SEED, 9L, 490, 217, 440);
+    assertBuckets(SPEC_SEED, -1L, 256, 641, 308);
+    assertBuckets(SPEC_SEED, Long.MIN_VALUE, 951, 0, 298);
+    assertBuckets(SPEC_SEED, "apple", 130, 747, 144);
+    assertBuckets(SPEC_SEED, "\u00e9t\u00e9", 806, 491, 163);
+    assertBuckets(42L, 1L, 468, 459, 696);
+    assertBuckets(42L, 9L, 841, 428, 322);
+  }
+
+  // 7.4 images
+  @Test
+  public void v2ImageVectors() {
+    final CountMinSketch empty = new CountMinSketch((byte) 2, 9, SPEC_SEED);
+    assertEquals(empty.getSerialVersion(), CountMinSketch.SERIAL_VERSION_2);
+    assertEquals(empty.toByteArray(), hex("02021201000000000900000002cc9300"));
+
+    final CountMinSketch cms = new CountMinSketch((byte) 2, 9, SPEC_SEED);
+    cms.update(1L, 10);
+    cms.update(9L, 810);
+    cms.update("apple", 5);
+    final byte[] expected = new byte[168];
+    System.arraycopy(hex("02021200000000000900000002cc9300"), 0, expected, 0, 
16);
+    ByteArrayUtil.putLongLE(expected, 16, 825);
+    ByteArrayUtil.putLongLE(expected, 24 + (8 * 0), 810);  // row 0, bucket 0
+    ByteArrayUtil.putLongLE(expected, 24 + (8 * 4), 5);    // row 0, bucket 4
+    ByteArrayUtil.putLongLE(expected, 24 + (8 * 6), 10);   // row 0, bucket 6
+    ByteArrayUtil.putLongLE(expected, 24 + (8 * 10), 5);   // row 1, bucket 1
+    ByteArrayUtil.putLongLE(expected, 24 + (8 * 11), 810); // row 1, bucket 2
+    ByteArrayUtil.putLongLE(expected, 24 + (8 * 16), 10);  // row 1, bucket 7
+    assertEquals(cms.toByteArray(), expected);
+
+    final CountMinSketch read = CountMinSketch.deserialize(expected, 
SPEC_SEED);
+    assertEquals(read.getSerialVersion(), CountMinSketch.SERIAL_VERSION_2);
+    assertEquals(read.getEstimate(1L), 10);
+    assertEquals(read.getEstimate(9L), 810);
+    assertEquals(read.getEstimate("apple"), 5);
+    assertEquals(read.toByteArray(), expected);
+  }
+
+  // The long overloads hash the 8 little-endian bytes of the item, like the 
byte[] overloads
+  @Test
+  public void v2LongMatchesLittleEndianBytes() {
+    final CountMinSketch a = new CountMinSketch((byte) 4, 101, SPEC_SEED);
+    final CountMinSketch b = new CountMinSketch((byte) 4, 101, SPEC_SEED);
+    final long[] items = { 0L, 1L, -1L, Long.MIN_VALUE, Long.MAX_VALUE, 
0x0123456789ABCDEFL };
+    for (final long item : items) {
+      final byte[] le = new byte[Long.BYTES];
+      ByteArrayUtil.putLongLE(le, 0, item);
+      a.update(item, 3);
+      b.update(le, 3);
+    }
+    assertEquals(a.toByteArray(), b.toByteArray());
+  }
+
+  // Version 1 images keep the legacy hashing and are written back as version 1
+  @Test
+  public void v1ImageKeepsLegacyHashing() {
+    final long seed = 1234L;
+    final byte numHashes = 3;
+    final int numBuckets = 17;
+    final byte[] emptyV1 = new CountMinSketch(numHashes, numBuckets, 
seed).toByteArray();
+    emptyV1[1] = CountMinSketch.SERIAL_VERSION_1;
+
+    final CountMinSketch v1 = CountMinSketch.deserialize(emptyV1, seed);
+    assertEquals(v1.getSerialVersion(), CountMinSketch.SERIAL_VERSION_1);
+    v1.update(7L, 11);
+    v1.update("legacy", 13);
+
+    final byte[] image = v1.toByteArray();
+    assertEquals(image[1], CountMinSketch.SERIAL_VERSION_1);
+
+    // Independent version 1 computation: seeds from Random(seed), 
MurmurHash3, floorMod, native byte order
+    final Random rand = new Random(seed);
+    final long[] rowSeeds = new long[numHashes];
+    for (int i = 0; i < numHashes; i++) { rowSeeds[i] = rand.nextLong(); }
+    final byte[] item7 = 
java.nio.ByteBuffer.allocate(8).order(java.nio.ByteOrder.nativeOrder()).putLong(7L).array();
+    final long[] expected = new long[numHashes * numBuckets];
+    for (int i = 0; i < numHashes; i++) {
+      expected[(i * numBuckets) + Math.floorMod(MurmurHash3.hash(item7, 
rowSeeds[i])[0], numBuckets)] += 11;
+      expected[(i * numBuckets) + 
Math.floorMod(MurmurHash3.hash(utf8("legacy"), rowSeeds[i])[0], numBuckets)] += 
13;
+    }
+    for (int k = 0; k < expected.length; k++) {
+      assertEquals(ByteArrayUtil.getLongLE(image, 24 + (8 * k)), expected[k], 
"counter " + k);
+    }
+
+    final CountMinSketch reread = CountMinSketch.deserialize(image, seed);
+    assertEquals(reread.getSerialVersion(), CountMinSketch.SERIAL_VERSION_1);
+    assertEquals(reread.getEstimate(7L), v1.getEstimate(7L));
+    assertEquals(reread.getEstimate("legacy"), v1.getEstimate("legacy"));
+  }
+
+  @Test
+  public void mergeAcrossVersionsThrows() {
+    final long seed = 1234L;
+    final byte[] emptyV1 = new CountMinSketch((byte) 3, 17, 
seed).toByteArray();
+    emptyV1[1] = CountMinSketch.SERIAL_VERSION_1;
+    final CountMinSketch v1 = CountMinSketch.deserialize(emptyV1, seed);
+    final CountMinSketch v2 = new CountMinSketch((byte) 3, 17, seed);
+    assertThrows(SketchesException.class, () -> v1.merge(v2));
+    assertThrows(SketchesException.class, () -> v2.merge(v1));
+  }
+
+  @Test
+  public void unknownSerialVersionThrows() {
+    final long seed = 1234L;
+    final byte[] image = new CountMinSketch((byte) 3, 17, seed).toByteArray();
+    image[1] = 3;
+    assertThrows(SketchesArgumentException.class, () -> 
CountMinSketch.deserialize(image, seed));
+    image[1] = 0;
+    assertThrows(SketchesArgumentException.class, () -> 
CountMinSketch.deserialize(image, seed));
+  }
+
+  @Test
+  public void nullAndEmptyItemsAreIgnored() {
+    final CountMinSketch cms = new CountMinSketch((byte) 3, 17, SPEC_SEED);
+    cms.update((byte[]) null, 5);
+    cms.update(new byte[0], 5);
+    cms.update((String) null, 5);
+    cms.update("", 5);
+    assertTrue(cms.isEmpty());
+    assertEquals(cms.getEstimate((byte[]) null), 0);
+    assertEquals(cms.getEstimate(new byte[0]), 0);
+    assertEquals(cms.getEstimate((String) null), 0);
+    assertEquals(cms.getEstimate(""), 0);
+    assertEquals(cms.getUpperBound((byte[]) null), 0);
+  }
+
+  private static void assertBuckets(final long seed, final long item, final 
int... buckets) {
+    final CountMinSketch cms = new CountMinSketch((byte) 3, 1000, seed);
+    cms.update(item, 1);
+    assertCounters(cms, buckets);
+  }
+
+  private static void assertBuckets(final long seed, final String item, final 
int... buckets) {
+    final CountMinSketch cms = new CountMinSketch((byte) 3, 1000, seed);
+    cms.update(item, 1);
+    assertCounters(cms, buckets);
+  }
+
+  private static void assertCounters(final CountMinSketch cms, final int... 
buckets) {
+    final byte[] image = cms.toByteArray();
+    for (int row = 0; row < buckets.length; row++) {
+      for (int b = 0; b < 1000; b++) {
+        final long counter = ByteArrayUtil.getLongLE(image, 24 + (8 * ((row * 
1000) + b)));
+        assertEquals(counter, b == buckets[row] ? 1 : 0, "row " + row + ", 
bucket " + b);
+      }
+    }
+  }
+
+  private static byte[] utf8(final String s) {
+    return s.getBytes(StandardCharsets.UTF_8);
+  }
+
+  private static byte[] hex(final String s) {
+    return HexFormat.of().parseHex(s);
+  }
+
 }


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to