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]