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

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


The following commit(s) were added to refs/heads/main by this push:
     new 4618600  feat(cpc): add union result serialization (#335)
4618600 is described below

commit 4618600b10952c354ac79afe38713277c38c75e9
Author: AhmedDusuki <[email protected]>
AuthorDate: Sat Nov 7 08:32:13 2026 +0200

    feat(cpc): add union result serialization (#335)
    
    Co-authored-by: tison <[email protected]>
---
 CHANGELOG.md                               |   1 +
 benchmarks/cpc/serde.rs                    |  40 +++++++++--
 datasketches/src/cpc/union.rs              | 104 ++++++++++++++++++-----------
 tests-integration/tests/serde_tests/cpc.rs |  57 ++++++++++++++++
 4 files changed, 159 insertions(+), 43 deletions(-)

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 1960df5..7d7158f 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -6,6 +6,7 @@ All significant changes to this project will be documented in 
this file.
 
 ### New features
 
+* Add `CpcUnion::serialize`, which produces the same bytes as 
`to_sketch().serialize()` and can be faster.
 * Add `HllUnion::serialize` to serialize union results directly.
 * Add `XorFilter` and `XorFilterBuilder` behind the `xor` feature for 
immutable membership queries on values or precomputed hashes. Filters support 
8-, 16-, and 32-bit fingerprints and can be serialized for later queries.
 
diff --git a/benchmarks/cpc/serde.rs b/benchmarks/cpc/serde.rs
index 5ea55ae..4259705 100644
--- a/benchmarks/cpc/serde.rs
+++ b/benchmarks/cpc/serde.rs
@@ -20,29 +20,50 @@ use std::hint::black_box;
 use benchmarks::Bencher;
 use benchmarks::Runner;
 use datasketches::cpc::CpcSketch;
+use datasketches::cpc::CpcUnion;
 
 const LG_K: u8 = 10;
+const UNION_LG_K: u8 = 18;
 
 fn serialize(bencher: Bencher, items: u64) {
-    let sketch = sketch(items);
+    let sketch = sketch(LG_K, items);
 
     bencher.bench_local(|| black_box(&sketch).serialize());
 }
 
 fn deserialize(bencher: Bencher, items: u64) {
-    let bytes = sketch(items).serialize();
+    let bytes = sketch(LG_K, items).serialize();
 
     bencher.bench_local(|| CpcSketch::deserialize(black_box(&bytes)).unwrap());
 }
 
-fn sketch(items: u64) -> CpcSketch {
-    let mut sketch = CpcSketch::new(LG_K).unwrap();
+fn serialize_union(bencher: Bencher, items: u64) {
+    let union = union(items);
+
+    bencher.bench_local(|| black_box(&union).serialize());
+}
+
+fn serialize_union_via_sketch(bencher: Bencher, items: u64) {
+    let union = union(items);
+
+    bencher.bench_local(|| black_box(&union).to_sketch().serialize());
+}
+
+fn sketch(lg_k: u8, items: u64) -> CpcSketch {
+    let mut sketch = CpcSketch::new(lg_k).unwrap();
     for value in 0..items {
         sketch.update(value);
     }
     sketch
 }
 
+fn union(items: u64) -> CpcUnion {
+    let sketch = sketch(UNION_LG_K, items);
+    let mut union = CpcUnion::new(UNION_LG_K).unwrap();
+    union.update(&sketch).unwrap();
+    union
+}
+
 pub fn register(runner: &mut Runner) {
     for &(items, rounds) in &[(200_u64, 400_000), (8_000_u64, 500_000)] {
         runner.case(format!("cpc::serde::serialize/{items:?}"), rounds, |b| {
@@ -54,4 +75,15 @@ pub fn register(runner: &mut Runner) {
             deserialize(b, items)
         });
     }
+    // Reuse each union for repeated serialization: empty, sparse, and 
bit-matrix results.
+    for &(items, rounds) in &[(0_u64, 4_000_000), (20_000_u64, 500), 
(80_000_u64, 200)] {
+        runner.compare(
+            &format!("cpc::serde::serialize_union/{items:?}"),
+            rounds,
+            &[
+                ("via sketch", &|b| serialize_union_via_sketch(b, items)),
+                ("direct", &|b| serialize_union(b, items)),
+            ],
+        );
+    }
 }
diff --git a/datasketches/src/cpc/union.rs b/datasketches/src/cpc/union.rs
index dac4f3a..c7691a4 100644
--- a/datasketches/src/cpc/union.rs
+++ b/datasketches/src/cpc/union.rs
@@ -53,13 +53,16 @@
 //! because of the partially inverted Logic in the Sliding flavor, where the 
presence of coupons
 //! is sometimes indicated by the ABSENCE of row_col pairs in the surprises 
table.)
 //!
-//! How does [`CpcUnion::to_sketch`] work?
+//! Result extraction and serialization:
 //!
-//! If the union has an Accumulator state, make a copy of that sketch.
+//! An accumulator is already a result sketch: [`CpcUnion::to_sketch`] clones 
it, while
+//! [`CpcUnion::serialize`] borrows it directly. Its estimator state must 
therefore be maintained
+//! during merging, including input adoption and downsampling, rather than 
repaired on export.
 //!
-//! If the union has a BitMatrix state, then we have to convert the bitMatrix 
back into a sketch,
-//! which requires doing some extra work to figure out the values of 
num_coupons, offset,
-//! first_interesting_column, and kxp.
+//! A bit matrix has no sliding window or surprise table. Both export paths 
reconstruct these,
+//! along with the coupon count, window offset, and first interesting column, 
through
+//! [`CpcUnion::to_sketch`]. The matrix does not preserve the stream history 
needed by HIP, so
+//! the reconstructed sketch uses the merged estimator.
 
 use std::fmt;
 
@@ -75,14 +78,29 @@ use crate::hash::DEFAULT_UPDATE_SEED;
 /// Union operator for CPC sketches.
 #[derive(Clone)]
 pub struct CpcUnion {
-    // immutable config variables
+    // Effective precision can decrease when merging a smaller sketch.
     lg_k: u8,
     seed: u64,
-
-    // union state
     state: UnionState,
 }
 
+/// Working representation of the union's coupon set.
+#[derive(Debug, Clone)]
+enum UnionState {
+    /// An empty or sparse sketch that can be exported directly.
+    ///
+    /// Every nonempty accumulator has `merge_flag = true`, including one 
adopted from a single
+    /// input. Union results use the merged estimator consistently, regardless 
of whether the
+    /// input's HIP history was retained by cloning or lost during table 
traversal.
+    /// Empty accumulators keep `merge_flag = false` to preserve the existing 
empty-result encoding.
+    Accumulator(CpcSketch),
+    /// A full coupon matrix, used once an input or the accumulator outgrows 
sparse mode.
+    ///
+    /// Row-wise OR combines coupon sets without maintaining a sketch's 
compressed layout or
+    /// estimator fields. Export must reconstruct that layout before it can 
use the sketch encoder.
+    BitMatrix(Vec<u64>),
+}
+
 impl Default for CpcUnion {
     fn default() -> Self {
         Self::new(DEFAULT_LG_K).unwrap()
@@ -105,7 +123,6 @@ impl CpcUnion {
     ///
     /// Returns an error if `lg_k` is not in the range `[4, 26]`, or the 
computed seed hash is zero.
     pub fn with_seed(lg_k: u8, seed: u64) -> Result<Self, Error> {
-        // We begin with the accumulator holding an EMPTY_MERGED sketch object.
         let sketch = CpcSketch::with_seed(lg_k, seed)?;
         let state = UnionState::Accumulator(sketch);
         Ok(Self { lg_k, seed, state })
@@ -143,16 +160,7 @@ impl CpcUnion {
     /// ```
     pub fn to_sketch(&self) -> CpcSketch {
         match &self.state {
-            UnionState::Accumulator(sketch) => {
-                if sketch.is_empty() {
-                    CpcSketch::with_seed(self.lg_k, self.seed).unwrap()
-                } else {
-                    let mut sketch = sketch.clone();
-                    assert_eq!(sketch.flavor(), Flavor::Sparse);
-                    sketch.merge_flag = true;
-                    sketch
-                }
-            }
+            UnionState::Accumulator(sketch) => sketch.clone(),
             UnionState::BitMatrix(matrix) => {
                 let lg_k = self.lg_k;
 
@@ -199,8 +207,8 @@ impl CpcUnion {
                     sketch.first_interesting_column = offset; // corner case
                 }
 
-                // HIP-related fields will contain zeros, and that is okay 
since merge_flag is true,
-                // and thus the HIP estimator will not be used.
+                // The matrix has no stream history, so the constructor's HIP 
fields cannot
+                // estimate this result. The merged estimator uses only lg_k 
and num_coupons.
                 sketch.sliding_window = sliding_window;
                 sketch.surprising_value_table = Some(table);
                 sketch.merge_flag = true;
@@ -210,6 +218,33 @@ impl CpcUnion {
         }
     }
 
+    /// Serializes the union's result as a `CpcSketch`.
+    ///
+    /// Produces the same bytes as [`Self::to_sketch`] followed by 
[`CpcSketch::serialize`],
+    /// and can be faster.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use datasketches::cpc::CpcSketch;
+    /// use datasketches::cpc::CpcUnion;
+    ///
+    /// let mut sketch = CpcSketch::new(12).unwrap();
+    /// sketch.update("apple");
+    ///
+    /// let mut union = CpcUnion::new(12).unwrap();
+    /// union.update(&sketch).unwrap();
+    ///
+    /// let result = CpcSketch::deserialize(&union.serialize()).unwrap();
+    /// assert_eq!(result.estimate(), union.to_sketch().estimate());
+    /// ```
+    pub fn serialize(&self) -> Vec<u8> {
+        match &self.state {
+            UnionState::Accumulator(sketch) => sketch.serialize(),
+            UnionState::BitMatrix(_) => self.to_sketch().serialize(),
+        }
+    }
+
     /// Updates this union with a `CpcSketch`.
     ///
     /// # Errors
@@ -254,14 +289,16 @@ impl CpcUnion {
                         );
                     }
 
-                    // The following partially fixes the snowplow problem 
provided that the K's
-                    // are equal.
+                    // Matching precision lets us reuse the table layout 
without reinserting
+                    // coupons. Adoption still produces a union result, so it 
must use the merged
+                    // estimator even though the cloned input may have a valid 
HIP history.
                     if old_flavor == Flavor::Empty && self.lg_k == 
sketch.lg_k() {
                         *old_sketch = sketch.clone();
+                        old_sketch.merge_flag = true;
                         return Ok(());
                     }
 
-                    walk_table_updating_sketch(old_sketch, 
sketch.surprising_value_table());
+                    merge_table_into_sketch(old_sketch, 
sketch.surprising_value_table());
                     let final_flavor = old_sketch.flavor();
 
                     // if the accumulator has graduated beyond sparse, switch 
to a bit matrix
@@ -322,7 +359,7 @@ impl CpcUnion {
                 }
 
                 let mut new_sketch = CpcSketch::with_seed(new_lg_k, 
self.seed).unwrap();
-                walk_table_updating_sketch(&mut new_sketch, 
sketch.surprising_value_table());
+                merge_table_into_sketch(&mut new_sketch, 
sketch.surprising_value_table());
 
                 let final_new_flavor = new_sketch.flavor();
                 // SV table had to have something in it
@@ -411,8 +448,10 @@ fn or_matrix_into_matrix(dst_matrix: &mut [u64], dst_lg_k: 
u8, src_matrix: &[u64
     }
 }
 
-fn walk_table_updating_sketch(sketch: &mut CpcSketch, table: &PairTable) {
+fn merge_table_into_sketch(sketch: &mut CpcSketch, table: &PairTable) {
     assert!(sketch.lg_k() <= 26);
+    // Table traversal cannot preserve the stream order required by the HIP 
estimator.
+    sketch.merge_flag = true;
 
     let slots = table.slots();
     let num_slots = slots.len() as u32;
@@ -438,16 +477,3 @@ fn walk_table_updating_sketch(sketch: &mut CpcSketch, 
table: &PairTable) {
         k += stride;
     }
 }
-
-/// The internal State of the Union operation.
-///
-/// At most one of BitMatrix and accumulator will be non-null at any given 
moment. Accumulator is a
-/// sketch object that is employed until it graduates out of Sparse mode.
-///
-/// At that point, it is converted into a full-sized bitMatrix, which is 
mathematically a sketch,
-/// but doesn't maintain any of the "extra" fields of our sketch objects.
-#[derive(Debug, Clone)]
-enum UnionState {
-    Accumulator(CpcSketch),
-    BitMatrix(Vec<u64>),
-}
diff --git a/tests-integration/tests/serde_tests/cpc.rs 
b/tests-integration/tests/serde_tests/cpc.rs
index 78c61fd..7df5df1 100644
--- a/tests-integration/tests/serde_tests/cpc.rs
+++ b/tests-integration/tests/serde_tests/cpc.rs
@@ -19,11 +19,68 @@ use std::fs;
 use std::path::Path;
 
 use datasketches::cpc::CpcSketch;
+use datasketches::cpc::CpcUnion;
 use googletest::assert_that;
 use googletest::prelude::near;
 
 use crate::serialization_test_data;
 
+#[test]
+fn test_union_serialization_matches_result() {
+    const LG_K: u8 = 11;
+    const SEED: u64 = 123;
+
+    // Empty, sparse, and bit-matrix union states.
+    for num_values in [0, 100, 2_000] {
+        let mut sketch = CpcSketch::with_seed(LG_K, SEED).unwrap();
+        for value in 0..num_values {
+            sketch.update(value);
+        }
+        let mut union = CpcUnion::with_seed(LG_K, SEED).unwrap();
+        union.update(&sketch).unwrap();
+
+        let bytes = union.serialize();
+        let result = union.to_sketch();
+        assert_eq!(bytes, result.serialize());
+        let decoded = CpcSketch::deserialize_with_seed(&bytes, SEED).unwrap();
+        assert_eq!(decoded.estimate(), result.estimate());
+    }
+}
+
+#[test]
+fn test_union_serialization_after_updates_and_downsampling() {
+    let mut union = CpcUnion::new(12).unwrap();
+    // Adopt a sparse input, accumulate overlapping inputs, downsample, fold a 
larger input,
+    // then promote to a bit matrix. Serialize between updates to check 
continued use.
+    for (lg_k, values) in [
+        (12, 0..40),
+        (12, 20..60),
+        (11, 50..100),
+        (12, 90..140),
+        (10, 100..2_000),
+    ] {
+        let mut sketch = CpcSketch::new(lg_k).unwrap();
+        for value in values.clone() {
+            sketch.update(value);
+        }
+        union.update(&sketch).unwrap();
+
+        // The same coupons must produce the same merged result regardless of 
stream order.
+        let mut reversed = CpcSketch::new(union.lg_k()).unwrap();
+        for value in (0..values.end).rev() {
+            reversed.update(value);
+        }
+        let mut reference = CpcUnion::new(union.lg_k()).unwrap();
+        reference.update(&reversed).unwrap();
+
+        let bytes = union.serialize();
+        assert_eq!(bytes, reference.to_sketch().serialize());
+        let decoded = CpcSketch::deserialize(&bytes).unwrap();
+        assert_eq!(decoded.lg_k(), union.lg_k());
+        assert_eq!(decoded.estimate(), union.to_sketch().estimate());
+    }
+}
+
 fn test_sketch_file(path: &Path, expected_cardinality: usize) -> CpcSketch {
     let expected = expected_cardinality as f64;
 


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

Reply via email to