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

leerho pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-tck.git


The following commit(s) were added to refs/heads/main by this push:
     new 7f03892  docs: add the Count-Min serialization format, version 2 (#21)
7f03892 is described below

commit 7f038924c9f4cd63803ec59148cfc4487f40780b
Author: Lee Rhodes <[email protected]>
AuthorDate: Thu Nov 12 12:03:24 2026 -0800

    docs: add the Count-Min serialization format, version 2 (#21)
    
    * docs: add the Count-Min serialization format, version 2
    
    Version 2 was agreed by lazy consensus in Discussion #18. The spec was
    posted there on 2026-11-02, and no objections were raised by the
    2026-11-09 deadline.
    
    The document covers the byte layout, row seed derivation, item encoding,
    item hashing and bucket mapping, operations and version handling, and
    test vectors. Item encoding includes placeholders for the shared input
    rules under discussion in #20: null and empty items, floating-point
    items, and other types. The README links the new document.
    
    Co-Authored-By: Claude Opus 5.5 <[email protected]>
    
    * docs: Count-Min v2, add the cross-language test files section
    
    Section 8 defines the version 2 CL files every implementation generates
    and checks: names (count_min_v2_<case>_<language>.sk), contents for each
    case, the checks a reader performs (including byte-identical images
    across languages), and how to treat the existing C++ version 1 files.
    
    Co-Authored-By: Claude Opus 5.5 <[email protected]>
    
    * docs: Count-Min v2, clarify upper bound and empty-item queries
    
    Applies Tison's review suggestions: section 8.2 refers to the upper
    bound returned by the sketch, and section 4.4 says every query on an
    ignored item (estimate, lower bound and upper bound) returns 0.
    
    Co-Authored-By: Claude Opus 5.5 <[email protected]>
    
    ---------
    
    Co-authored-by: Claude Opus 5.5 <[email protected]>
---
 README.md                |   4 +
 docs/count-min-format.md | 253 +++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 257 insertions(+)

diff --git a/README.md b/README.md
index 0168d81..b234b9b 100644
--- a/README.md
+++ b/README.md
@@ -14,6 +14,10 @@ This repository contains snapshots of serialized sketches, 
which a particular Da
 
 See [Serialization snapshots](docs/serialization-snapshots.md) for the 
repository design, the snapshot generation commands, and the maintainer 
workflow for updating the corpus from an upstream DataSketches implementation.
 
+Format specifications:
+
+- [Count-Min sketch, serialization format version 2](docs/count-min-format.md)
+
 ## Contribute
 
 Please visit the main [DataSketches website](https://datasketches.apache.org) 
for more information.
diff --git a/docs/count-min-format.md b/docs/count-min-format.md
new file mode 100644
index 0000000..77896c6
--- /dev/null
+++ b/docs/count-min-format.md
@@ -0,0 +1,253 @@
+<!--
+  Licensed to the Apache Software Foundation (ASF) under one or more
+  contributor license agreements. See the NOTICE file distributed with
+  this work for additional information regarding copyright ownership.
+  The ASF licenses this file to You under the Apache License, Version 2.0
+  (the "License"); you may not use this file except in compliance with
+  the License. You may obtain a copy of the License at
+
+      http://www.apache.org/licenses/LICENSE-2.0
+
+  Unless required by applicable law or agreed to in writing, software
+  distributed under the License is distributed on an "AS IS" BASIS,
+  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+  See the License for the specific language governing permissions and
+  limitations under the License.
+-->
+
+# Count-Min sketch: serialization format, version 2
+
+**Status:** adopted. The design was agreed by lazy consensus in [Discussion 
#18](https://github.com/apache/datasketches-tck/discussions/18), which closed 
on 2026-10-25. This spec was posted there on 2026-11-02, and no objections were 
raised by the 2026-11-09 deadline.
+
+This spec defines everything a Count-Min implementation needs in order to read 
and write images that work in every language: the byte layout, how row seeds 
are derived, how items are encoded and hashed, and how a hash maps to a bucket. 
An image written by any conforming implementation gives the same estimates, 
updates and merges in every other one. Identical inputs produce byte-identical 
images.
+
+Version 2 differs from version 1 only in the serial version byte and in the 
hashing (sections 3 to 5). The byte layout is unchanged.
+
+## 1. Parameters
+
+| Parameter | Type | Valid range |
+|---|---|---|
+| `numHashes` (rows) | unsigned 8-bit | 1 to 127 (Java and Go store it as a 
signed byte) |
+| `numBuckets` (columns) | unsigned 32-bit | at least 3, and `numHashes × 
numBuckets < 2^30` |
+| `seed` (base seed) | 64-bit | any; the library default is 9001 |
+
+## 2. Byte layout
+
+All multi-byte fields are little-endian.
+
+| Byte offset | Size | Field | Value |
+|---:|---:|---|---|
+| 0 | 1 | preamble longs | 2 |
+| 1 | 1 | serial version | **2** |
+| 2 | 1 | family ID | 18 (Count-Min) |
+| 3 | 1 | flags | bit 0: `IS_EMPTY`; other bits 0 |
+| 4 | 4 | unused | 0 |
+| 8 | 4 | `numBuckets` | unsigned 32-bit |
+| 12 | 1 | `numHashes` | unsigned 8-bit |
+| 13 | 2 | seed hash | the standard DataSketches 16-bit seed hash of `seed`, 
as used by Theta; 9001 gives `0x93CC` |
+| 15 | 1 | unused | 0 |
+| 16 | 8 | total weight | signed 64-bit; present only if not empty |
+| 24 | 8 × `numHashes` × `numBuckets` | counters | signed 64-bit each; present 
only if not empty |
+
+- A sketch is empty when its total weight is 0. An empty image is exactly 16 
bytes and has `IS_EMPTY` set.
+- A non-empty image is `24 + 8 × numHashes × numBuckets` bytes.
+- Counters are stored row by row. The counter for row `i`, bucket `b` is at 
index `i × numBuckets + b`, which is byte offset `24 + 8 × (i × numBuckets + 
b)`.
+- Counters and total weight are signed 64-bit, two's complement. An 
implementation with a different counter type (such as C++ with a non-`int64_t` 
weight type) can't write images that other languages read.
+
+Readers check the preamble longs, the family ID, the serial version (section 
6) and the seed hash, and that the image is long enough for its declared size.
+
+## 3. Row seeds
+
+Each row hashes items with its own 64-bit row seed, derived from the base seed:
+
+```
+rowSeed[i] = XXH64(LE64(i), seed = baseSeed)        for i = 0 .. numHashes - 1
+```
+
+- `XXH64` is the 64-bit xxHash, as defined by the [xxHash 
specification](https://github.com/Cyan4973/xxHash/blob/dev/doc/xxhash_spec.md).
+- `LE64(i)` is the row index as 8 bytes, little-endian.
+- Nothing is added to the result; in particular there is no `+ baseSeed`.
+- Row seeds are never stored in the image. Readers derive them from the seed 
they are given, after checking the seed hash.
+
+## 4. Item encoding
+
+An item is hashed as a byte sequence. Every implementation must produce 
exactly the bytes defined in this section. Implementations must not pass items 
through a language's generic hashing framework, because those add bytes of 
their own. For example, Rust's `Hash` trait adds `0xFF` after a string and an 
8-byte length before a byte slice.
+
+Sections 4.4 to 4.6 are placeholders for input rules that apply to every 
DataSketches family. They are being discussed in [Discussion 
#20](https://github.com/apache/datasketches-tck/discussions/20). Each 
placeholder states what version 2 requires today. When the shared rules are 
agreed, they will be specified in one place and referenced from here.
+
+### 4.1 Integers
+
+| Item type | Bytes hashed |
+|---|---|
+| 64-bit integer, signed or unsigned | 8 bytes, little-endian, two's 
complement |
+| Narrower integer | widened to 64 bits first (sign-extended if signed), then 
as above |
+
+### 4.2 Strings
+
+A string is hashed as its UTF-8 bytes, with no length prefix and no terminator.
+
+- UTF-8 is the only string encoding version 2 defines. An implementation whose 
native strings use another encoding converts them to UTF-8 before hashing.
+- Java has historical APIs in other families that use UTF-16 (for example 
`update(char[])` in Theta, HLL, CPC, Bloom and Xor, and 
`ArrayOfUtf16StringsSerDe`). They don't apply to Count-Min.
+
+### 4.3 Byte arrays
+
+A byte array is hashed as the bytes given, in order.
+
+### 4.4 Null and empty items (placeholder)
+
+**Version 2 rule:** an empty string, an empty byte array (zero length, such as 
Java `new byte[0]`), and a null, in languages that have one, are all ignored. 
An update does nothing, and every query (estimate, lower bound, and upper 
bound) returns 0.
+
+**Pending (Discussion #20):** a shared policy for every family, covering:
+- how a reader or an update interprets a null item;
+- how it interprets an empty item (empty string, zero-length byte array, empty 
array);
+- when an implementation may emit, store or return a null or an empty object.
+
+### 4.5 Floating-point items (placeholder)
+
+**Version 2 rule:** floating-point items are not defined for this sketch. 
Users convert them to one of the types above.
+
+**Pending (Discussion #20):** if a later version accepts floating-point items, 
they must be canonicalized before hashing, as HLL, CPC, Theta and Tuple already 
do:
+- `-0.0` and `+0.0` must hash as one item, `+0.0`;
+- every NaN must hash as one canonical NaN. Java's `Double.doubleToLongBits` 
produces `0x7FF8000000000000`; other languages must state how they produce the 
same bits.
+
+### 4.6 Other types (placeholder)
+
+**Version 2 rule:** other types (booleans, arrays of numbers, composite 
values) are not defined for this sketch. Users convert them to one of the types 
above.
+
+**Pending:** any later type must define its exact bytes here, independent of 
any language's in-memory representation.
+
+## 5. Item hashing and bucket mapping
+
+For row `i`:
+
+```
+h      = XXH64(itemBytes, seed = rowSeed[i])        // unsigned 64-bit
+bucket = (h >>> 1) mod numBuckets
+index  = i × numBuckets + bucket
+```
+
+The shift by one clears the top bit, so the result is the same whether a 
language's 64-bit integers are signed or unsigned. Theta, Tuple and the Bloom 
filter already use this convention.
+
+## 6. Operations and versions
+
+- **Update** `(item, weight)`: the total weight increases by `|weight|`, and 
in each row the counter at the item's index increases by `weight`.
+- **Estimate**: the minimum of the item's counters over all rows. The upper 
and lower bounds are unchanged from version 1.
+- **Merge**: requires equal `numHashes`, `numBuckets` and seed, and the same 
serial version. Counters and total weights are added.
+- **Writing**: new sketches are written as version 2.
+- **Reading version 1**: readers accept version 1 images and use the 
language's own legacy (version 1) row seeds and bucket mapping for them. A 
sketch read from a version 1 image keeps the legacy hashing and is written back 
as version 1, so its counters are never labeled with the wrong algorithm. 
Version 1 sketches can't be merged with version 2 sketches. Version 1 images 
remain unreliable across languages, and in C++ across standard libraries.
+- **Other versions** are rejected.
+
+## 7. Test vectors
+
+These were computed with the DataSketches Java `XxHash64`. The bucket results 
for seeds 9001 and 42 match the independently computed vectors in 
[apache/datasketches-rust#299](https://github.com/apache/datasketches-rust/pull/299).
+
+### 7.1 XXH64
+
+| Input | Seed | XXH64 |
+|---|---:|---|
+| empty | 0 | `0xEF46DB3751D8E999` |
+| `"a"` | 0 | `0xD24EC4F1A98C6E5B` |
+| `"abc"` | 0 | `0x44BC2CF5AD770999` |
+
+### 7.2 Row seeds
+
+| Base seed | Row 0 | Row 1 | Row 2 |
+|---:|---|---|---|
+| 9001 | `0xD71D64972584A288` | `0xEFE8454A6499F311` | `0x23819BE21B1B1D9E` |
+| 42 | `0xB71B47EBDA15746C` | `0x9ED50FD59358D232` | `0xD19FE30002B9A3CD` |
+
+### 7.3 Item hashes and buckets
+
+Base seed 9001, `numBuckets` = 1000. Each cell shows `XXH64(item, rowSeed[i])` 
and the bucket.
+
+| Item | Row 0 | Row 1 | Row 2 |
+|---|---|---|---|
+| integer 1 | `0x9578D22909AB6393` → 185 | `0x73BE69FFC52746B5` → 898 | 
`0xA16D5BA2EA9D92A9` → 4 |
+| integer 9 | `0xE351D001EE0C0725` → 490 | `0x74AB8E217F6C0193` → 217 | 
`0x4E02535F97CE07D1` → 440 |
+| integer -1 | `0x295F6FF9D5F0A170` → 256 | `0x693A5A4C04C19D72` → 641 | 
`0xC3095F604CF42A69` → 308 |
+| integer `0x8000000000000000` | `0x69DD53CB2E1960EE` → 951 | 
`0xBE1283E430FCA711` → 0 | `0x62BD4CDD3889A7D5` → 298 |
+| string `"apple"` | `0x0F686B647380AF74` → 130 | `0x25329624EF6A5FF6` → 747 | 
`0x501EE67250FD0E21` → 144 |
+| string `"été"` (UTF-8 `c3 a9 74 c3 a9`) | `0x38F345607F8C14EC` → 806 | 
`0x75787F10A22C78A7` → 491 | `0x43BEC0D845165366` → 163 |
+
+Several of these hashes have the top bit set, so an implementation that skips 
the shift or treats the hash as signed gets different buckets.
+
+With base seed 42, integer 1 maps to buckets 468, 459, 696 and integer 9 to 
841, 428, 322.
+
+### 7.4 Images
+
+Base seed 9001, `numHashes` = 2, `numBuckets` = 9.
+
+Empty (16 bytes):
+
+```
+02 02 12 01 00 00 00 00  09 00 00 00 02 cc 93 00
+```
+
+After `update(1, 10)`, `update(9, 810)` and `update("apple", 5)` (168 bytes). 
Row 0 puts 9, `"apple"` and 1 in buckets 0, 4 and 6; row 1 puts `"apple"`, 9 
and 1 in buckets 1, 2 and 7. The total weight is 825.
+
+```
+  0: 02 02 12 00 00 00 00 00   preamble: version 2, family 18, not empty
+  8: 09 00 00 00 02 cc 93 00   numBuckets 9, numHashes 2, seed hash 0x93CC
+ 16: 39 03 00 00 00 00 00 00   total weight 825
+ 24: 2a 03 00 00 00 00 00 00   row 0, bucket 0: 810
+ 32: 00 00 00 00 00 00 00 00
+ 40: 00 00 00 00 00 00 00 00
+ 48: 00 00 00 00 00 00 00 00
+ 56: 05 00 00 00 00 00 00 00   row 0, bucket 4: 5
+ 64: 00 00 00 00 00 00 00 00
+ 72: 0a 00 00 00 00 00 00 00   row 0, bucket 6: 10
+ 80: 00 00 00 00 00 00 00 00
+ 88: 00 00 00 00 00 00 00 00
+ 96: 00 00 00 00 00 00 00 00   row 1, bucket 0
+104: 05 00 00 00 00 00 00 00   row 1, bucket 1: 5
+112: 2a 03 00 00 00 00 00 00   row 1, bucket 2: 810
+120: 00 00 00 00 00 00 00 00
+128: 00 00 00 00 00 00 00 00
+136: 00 00 00 00 00 00 00 00
+144: 00 00 00 00 00 00 00 00
+152: 0a 00 00 00 00 00 00 00   row 1, bucket 7: 10
+160: 00 00 00 00 00 00 00 00
+```
+
+Reading this image back with seed 9001 gives estimates of 10 for 1, 810 for 9 
and 5 for `"apple"`.
+
+## 8. Cross-language test files
+
+Each implementation generates the files below into its 
`serialization_test_data/<language>_generated_files` directory, as described in 
[Serialization snapshots](serialization-snapshots.md), and checks the files 
generated by the other languages.
+
+### 8.1 Names and contents
+
+File names have the form `count_min_v2_<case>_<language>.sk`, where 
`<language>` is the implementation's snapshot suffix (for example `cpp`, `go`, 
`java` or `rust`).
+
+Every file uses `numHashes` = 3 and `numBuckets` = 1000.
+
+| Case | Seed | `N` |
+|---|---:|---:|
+| `n0` | 9001 | 0 (empty) |
+| `n1` | 9001 | 1 |
+| `n10` | 9001 | 10 |
+| `n100` | 9001 | 100 |
+| `n1000` | 9001 | 1000 |
+| `n10000` | 9001 | 10000 |
+| `seed42_n1000` | 42 | 1000 |
+
+For each `i` from 0 to `N - 1`, the sketch is updated twice:
+- with the 64-bit integer `i` and weight `i + 1`;
+- with the string of `i` in decimal (`"0"`, `"1"`, ..., with no sign, padding 
or separators) and weight 1.
+
+The total weight is therefore `N × (N + 1) / 2 + N`.
+
+Version 2 is deterministic, so a file with a given case must be 
**byte-identical** in every language. For example, `count_min_v2_n1000_cpp.sk` 
and `count_min_v2_n1000_java.sk` contain the same bytes.
+
+### 8.2 Checks
+
+A reader checks each file from another language as follows:
+- It deserializes with the file's seed and reports serial version 2, 
`numHashes` 3 and `numBuckets` 1000.
+- It is empty if and only if `N` = 0.
+- The total weight is `N × (N + 1) / 2 + N`.
+- For each `i` from 0 to `N - 1`, the estimate for integer `i` is at least `i 
+ 1`, and the estimate for the string of `i` is at least 1. All weights are 
positive, so a Count-Min sketch never underestimates. Each estimate is also at 
most the upper bound returned by the sketch for that item.
+- If the reader's own language has generated the same case, the two files are 
equal byte for byte. This is the strongest check, because it covers the row 
seeds, item encoding and bucket mapping at once.
+
+### 8.3 Version 1 files
+
+The existing files `count_min_empty_cpp.sk` and `count_min_non_empty_cpp.sk` 
are version 1 images. Readers may check that they deserialize as version 1 
sketches, but shouldn't compare their estimates across languages, because 
version 1 hashing differs between languages. Version 2 files always use the 
`count_min_v2_` prefix, so these names are never reused for version 2 images.


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

Reply via email to