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 4987426  feat(hll,theta): support target HllType in 
HllUnion::serialize and add ThetaUnion::serialize_compressed (#369)
4987426 is described below

commit 498742694821984cccadd97c3acff451afdf3e9c
Author: tison <[email protected]>
AuthorDate: Sun Nov 15 19:09:32 2026 +0800

    feat(hll,theta): support target HllType in HllUnion::serialize and add 
ThetaUnion::serialize_compressed (#369)
---
 CHANGELOG.md                                       |   2 +-
 benchmarks/hll/serde.rs                            |  55 ++--
 datasketches/src/hll/array4.rs                     |  44 +---
 datasketches/src/hll/array6.rs                     |  46 +---
 datasketches/src/hll/array8.rs                     | 207 +++++++++++++--
 datasketches/src/hll/serialization.rs              |  42 +++
 datasketches/src/hll/union.rs                      | 292 +++++++++------------
 .../src/thetafamily/theta/serialization.rs         |  90 +++++++
 datasketches/src/thetafamily/theta/sketch.rs       |  88 +------
 datasketches/src/thetafamily/theta/union.rs        |  42 ++-
 tests-integration/tests/hll_test/union.rs          |  37 ++-
 tests-integration/tests/serde_tests/hll.rs         | 176 ++++++++++++-
 tests-integration/tests/serde_tests/theta.rs       |  95 +++++++
 13 files changed, 830 insertions(+), 386 deletions(-)

diff --git a/CHANGELOG.md b/CHANGELOG.md
index a6414f7..cebd4c3 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -19,7 +19,7 @@ All significant changes to this project will be documented in 
this file.
 
 ### New features
 
-* Add `CpcUnion::serialize`, `HllUnion::serialize`, `ThetaUnion::serialize`, 
and `TupleUnion::serialize` to encode union results without calling 
`to_sketch`. Direct serialization avoids intermediate sketch allocations for 
`HllUnion` and `CpcUnion`, writes an `HllType::Hll8` image at the union's 
effective `lg_k` for `HllUnion`, and encodes `TupleUnion` summaries without 
requiring `Clone` or cloning heap-backed summaries.
+* Add `CpcUnion::serialize`, `HllUnion::serialize`, `ThetaUnion::serialize`, 
`ThetaUnion::serialize_compressed`, and `TupleUnion::serialize` to encode union 
results without calling `to_sketch`. Direct serialization avoids intermediate 
sketch allocations for `HllUnion` and `CpcUnion`, lets `HllUnion::serialize` 
target any `HllType` (`Hll4`, `Hll6`, or `Hll8`) at the union's effective 
`lg_k`, supports v4 compressed output via `ThetaUnion::serialize_compressed`, 
and encodes `TupleUnion` sum [...]
 * Add `XorFilter`, `XorFilterBuilder`, and `XorFilterType` 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.
 
 ### Improvements
diff --git a/benchmarks/hll/serde.rs b/benchmarks/hll/serde.rs
index de9fa35..d193703 100644
--- a/benchmarks/hll/serde.rs
+++ b/benchmarks/hll/serde.rs
@@ -30,35 +30,42 @@ fn union(rows: u64) -> HllUnion {
     union
 }
 
-fn serialize_union(bencher: Bencher, rows: u64) {
+fn serialize_union(bencher: Bencher, rows: u64, hll_type: HllType, direct: 
bool) {
     let union = union(rows);
-    bencher.bench_local(|| black_box(&union).serialize());
-}
-
-fn serialize_union_via_sketch(bencher: Bencher, rows: u64) {
-    let union = union(rows);
-    bencher.bench_local(|| 
black_box(&union).to_sketch(HllType::Hll8).serialize());
+    if direct {
+        bencher.bench_local(|| black_box(&union).serialize(hll_type));
+    } else {
+        bencher.bench_local(|| 
black_box(&union).to_sketch(hll_type).serialize());
+    }
 }
 
 pub fn register(runner: &mut Runner) {
-    let cases = &[
-        (0, 15_000_000),
-        (4, 12_000_000),
-        (100, 2_000_000),
-        (80_000, 90_000),
+    let targets = [
+        ("hll4", HllType::Hll4, 500),
+        ("hll6", HllType::Hll6, 600),
+        ("hll8", HllType::Hll8, 50_000),
     ];
-    for &(rows, rounds) in cases {
-        runner.case(
-            format!("hll::serde::serialize_union/{rows:?}"),
-            rounds,
-            |b| serialize_union(b, rows),
-        );
-    }
-    for &(rows, rounds) in cases {
-        runner.case(
-            format!("hll::serde::serialize_union_via_sketch/{rows:?}"),
-            rounds,
-            |b| serialize_union_via_sketch(b, rows),
+    let sparse_cases = [(0, 10_000_000), (4, 8_000_000), (100, 1_500_000)];
+    for &(label, hll_type, dense_rounds) in &targets {
+        for &(rows, rounds) in &sparse_cases {
+            runner.compare(
+                &format!("hll::serde::serialize_union/{label}/{rows:?}"),
+                rounds,
+                &[
+                    ("via_sketch", &|b| serialize_union(b, rows, hll_type, 
false)),
+                    ("direct", &|b| serialize_union(b, rows, hll_type, true)),
+                ],
+            );
+        }
+        runner.compare(
+            &format!("hll::serde::serialize_union/{label}/80000"),
+            dense_rounds,
+            &[
+                ("via_sketch", &|b| {
+                    serialize_union(b, 80_000, hll_type, false)
+                }),
+                ("direct", &|b| serialize_union(b, 80_000, hll_type, true)),
+            ],
         );
     }
 }
diff --git a/datasketches/src/hll/array4.rs b/datasketches/src/hll/array4.rs
index 4190a3f..28daa80 100644
--- a/datasketches/src/hll/array4.rs
+++ b/datasketches/src/hll/array4.rs
@@ -18,24 +18,18 @@
 use crate::codec::SketchBytes;
 use crate::codec::SketchSlice;
 use crate::codec::assert::insufficient_data;
-use crate::codec::family::Family;
 use crate::common::NumStdDev;
 use crate::error::Error;
 use crate::hll::Coupon;
+use crate::hll::HllType;
 use crate::hll::aux_map::AuxMap;
 use crate::hll::estimator::EstimateState;
 use crate::hll::estimator::Estimator;
-use crate::hll::serialization::COMPACT_FLAG_MASK;
 use crate::hll::serialization::COUPON_SIZE_BYTES;
-use crate::hll::serialization::CUR_MODE_HLL;
 use crate::hll::serialization::HLL_PREAMBLE_SIZE;
-use crate::hll::serialization::HLL_PREINTS;
-use crate::hll::serialization::OUT_OF_ORDER_FLAG_MASK;
-use crate::hll::serialization::SERIAL_VERSION;
-use crate::hll::serialization::TGT_HLL4;
-use crate::hll::serialization::encode_mode_byte;
+use crate::hll::serialization::write_hll_preamble;
 
-const AUX_TOKEN: u8 = 15;
+pub const AUX_TOKEN: u8 = 15;
 
 #[derive(Clone, Copy)]
 pub enum AuxFormat {
@@ -386,29 +380,15 @@ impl Array4 {
         let total_size = HLL_PREAMBLE_SIZE + num_bytes + (aux_count as usize * 
COUPON_SIZE_BYTES);
         let mut bytes = SketchBytes::with_capacity(total_size);
 
-        bytes.write_u8(HLL_PREINTS);
-        bytes.write_u8(SERIAL_VERSION);
-        bytes.write_u8(Family::HLL.id);
-        bytes.write_u8(lg_config_k);
-        bytes.write_u8(0); // lg_arr is unused for compact auxiliary storage.
-
-        let mut flags = COMPACT_FLAG_MASK;
-        if self.estimator.uses_composite_estimate() {
-            flags |= OUT_OF_ORDER_FLAG_MASK;
-        }
-        bytes.write_u8(flags);
-
-        bytes.write_u8(self.cur_min);
-
-        bytes.write_u8(encode_mode_byte(CUR_MODE_HLL, TGT_HLL4));
-
-        bytes.write_f64_le(self.estimator.hip_accum());
-        bytes.write_f64_le(self.estimator.kxq0());
-        bytes.write_f64_le(self.estimator.kxq1());
-
-        bytes.write_u32_le(self.num_at_cur_min);
-
-        bytes.write_u32_le(aux_count);
+        write_hll_preamble(
+            &mut bytes,
+            lg_config_k,
+            HllType::Hll4,
+            self.cur_min,
+            self.num_at_cur_min,
+            aux_count,
+            &self.estimator,
+        );
 
         bytes.write(&self.bytes);
 
diff --git a/datasketches/src/hll/array6.rs b/datasketches/src/hll/array6.rs
index 636da15..b1fe163 100644
--- a/datasketches/src/hll/array6.rs
+++ b/datasketches/src/hll/array6.rs
@@ -18,19 +18,14 @@
 use crate::codec::SketchBytes;
 use crate::codec::SketchSlice;
 use crate::codec::assert::insufficient_data;
-use crate::codec::family::Family;
 use crate::common::NumStdDev;
 use crate::error::Error;
 use crate::hll::Coupon;
+use crate::hll::HllType;
 use crate::hll::estimator::EstimateState;
 use crate::hll::estimator::Estimator;
-use crate::hll::serialization::CUR_MODE_HLL;
 use crate::hll::serialization::HLL_PREAMBLE_SIZE;
-use crate::hll::serialization::HLL_PREINTS;
-use crate::hll::serialization::OUT_OF_ORDER_FLAG_MASK;
-use crate::hll::serialization::SERIAL_VERSION;
-use crate::hll::serialization::TGT_HLL6;
-use crate::hll::serialization::encode_mode_byte;
+use crate::hll::serialization::write_hll_preamble;
 
 const VAL_MASK_6: u16 = 0x3F;
 
@@ -201,32 +196,15 @@ impl Array6 {
         let total_size = HLL_PREAMBLE_SIZE + num_bytes;
         let mut bytes = SketchBytes::with_capacity(total_size);
 
-        bytes.write_u8(HLL_PREINTS);
-        bytes.write_u8(SERIAL_VERSION);
-        bytes.write_u8(Family::HLL.id);
-        bytes.write_u8(lg_config_k);
-        bytes.write_u8(0); // unused for HLL mode
-
-        let mut flags = 0u8;
-        if self.estimator.uses_composite_estimate() {
-            flags |= OUT_OF_ORDER_FLAG_MASK;
-        }
-        bytes.write_u8(flags);
-
-        // cur_min is always 0 for Array6
-        bytes.write_u8(0);
-
-        bytes.write_u8(encode_mode_byte(CUR_MODE_HLL, TGT_HLL6));
-
-        bytes.write_f64_le(self.estimator.hip_accum());
-        bytes.write_f64_le(self.estimator.kxq0());
-        bytes.write_f64_le(self.estimator.kxq1());
-
-        // Write num_at_cur_min (num_zeros for Array6)
-        bytes.write_u32_le(self.num_zeros);
-
-        // Write aux_count (always 0 for Array6)
-        bytes.write_u32_le(0);
+        write_hll_preamble(
+            &mut bytes,
+            lg_config_k,
+            HllType::Hll6,
+            0,
+            self.num_zeros,
+            0,
+            &self.estimator,
+        );
 
         bytes.write(&self.bytes);
 
@@ -239,7 +217,7 @@ impl Array6 {
     }
 }
 
-fn num_bytes_for_k(k: u32) -> usize {
+pub fn num_bytes_for_k(k: u32) -> usize {
     // The final register's 16-bit read/write window needs one padding byte.
     (((k * 3) >> 2) + 1) as usize
 }
diff --git a/datasketches/src/hll/array8.rs b/datasketches/src/hll/array8.rs
index 6586104..f45fdae 100644
--- a/datasketches/src/hll/array8.rs
+++ b/datasketches/src/hll/array8.rs
@@ -20,19 +20,17 @@ use std::sync::OnceLock;
 use crate::codec::SketchBytes;
 use crate::codec::SketchSlice;
 use crate::codec::assert::insufficient_data;
-use crate::codec::family::Family;
 use crate::common::NumStdDev;
 use crate::error::Error;
 use crate::hll::Coupon;
+use crate::hll::HllType;
+use crate::hll::array4::AUX_TOKEN;
+use crate::hll::array6::num_bytes_for_k;
 use crate::hll::estimator::EstimateState;
 use crate::hll::estimator::Estimator;
-use crate::hll::serialization::CUR_MODE_HLL;
+use crate::hll::serialization::COUPON_SIZE_BYTES;
 use crate::hll::serialization::HLL_PREAMBLE_SIZE;
-use crate::hll::serialization::HLL_PREINTS;
-use crate::hll::serialization::OUT_OF_ORDER_FLAG_MASK;
-use crate::hll::serialization::SERIAL_VERSION;
-use crate::hll::serialization::TGT_HLL8;
-use crate::hll::serialization::encode_mode_byte;
+use crate::hll::serialization::write_hll_preamble;
 
 /// Registers stored one per byte.
 #[derive(Debug, Clone)]
@@ -300,38 +298,102 @@ impl Array8 {
 
     pub fn serialize(&self, lg_config_k: u8) -> Vec<u8> {
         let estimation = self.estimation();
-        let k = 1 << lg_config_k;
-        let total_size = HLL_PREAMBLE_SIZE + k as usize;
+        let k = 1usize << lg_config_k;
+        let total_size = HLL_PREAMBLE_SIZE + k;
         let mut bytes = SketchBytes::with_capacity(total_size);
 
-        bytes.write_u8(HLL_PREINTS);
-        bytes.write_u8(SERIAL_VERSION);
-        bytes.write_u8(Family::HLL.id);
-        bytes.write_u8(lg_config_k);
-        bytes.write_u8(0); // unused for HLL mode
+        write_hll_preamble(
+            &mut bytes,
+            lg_config_k,
+            HllType::Hll8,
+            0,
+            estimation.num_zeros,
+            0,
+            &estimation.estimator,
+        );
+
+        bytes.write(&self.bytes);
 
-        let mut flags = 0u8;
-        if estimation.estimator.uses_composite_estimate() {
-            flags |= OUT_OF_ORDER_FLAG_MASK;
+        bytes.into_bytes()
+    }
+
+    pub fn serialize_as(&self, lg_config_k: u8, hll_type: HllType) -> Vec<u8> {
+        match hll_type {
+            HllType::Hll4 => self.serialize_as_hll4(lg_config_k),
+            HllType::Hll6 => self.serialize_as_hll6(lg_config_k),
+            HllType::Hll8 => self.serialize(lg_config_k),
         }
-        bytes.write_u8(flags);
+    }
 
-        // cur_min is always 0 for Array8
+    fn serialize_as_hll6(&self, lg_config_k: u8) -> Vec<u8> {
+        let estimation = self.estimation();
+        let k = 1u32 << lg_config_k;
+        let num_bytes = num_bytes_for_k(k);
+        let total_size = HLL_PREAMBLE_SIZE + num_bytes;
+        let mut bytes = SketchBytes::with_capacity(total_size);
+
+        write_hll_preamble(
+            &mut bytes,
+            lg_config_k,
+            HllType::Hll6,
+            0,
+            estimation.num_zeros,
+            0,
+            &estimation.estimator,
+        );
+
+        for chunk in self.bytes.chunks_exact(4) {
+            let v0 = chunk[0].min(63);
+            let v1 = chunk[1].min(63);
+            let v2 = chunk[2].min(63);
+            let v3 = chunk[3].min(63);
+            bytes.write(&[v0 | (v1 << 6), (v1 >> 2) | (v2 << 4), (v2 >> 4) | 
(v3 << 2)]);
+        }
+        // Array6 reads and writes 16-bit windows and expects one trailing 
padding byte.
         bytes.write_u8(0);
 
-        bytes.write_u8(encode_mode_byte(CUR_MODE_HLL, TGT_HLL8));
+        bytes.into_bytes()
+    }
+
+    fn serialize_as_hll4(&self, lg_config_k: u8) -> Vec<u8> {
+        let estimation = self.estimation();
+        let k = 1usize << lg_config_k;
 
-        bytes.write_f64_le(estimation.estimator.hip_accum());
-        bytes.write_f64_le(estimation.estimator.kxq0());
-        bytes.write_f64_le(estimation.estimator.kxq1());
+        let cur_min = self.bytes.iter().copied().min().unwrap_or(0);
+        let mut num_at_cur_min = 0u32;
+        let mut aux_count = 0usize;
+        for &val in &self.bytes {
+            num_at_cur_min += u32::from(val == cur_min);
+            aux_count += usize::from(val - cur_min >= AUX_TOKEN);
+        }
 
-        // Write num_at_cur_min (num_zeros for Array8)
-        bytes.write_u32_le(estimation.num_zeros);
+        let num_bytes = k >> 1;
+        let total_size = HLL_PREAMBLE_SIZE + num_bytes + (aux_count * 
COUPON_SIZE_BYTES);
+        let mut bytes = SketchBytes::with_capacity(total_size);
 
-        // Write aux_count (always 0 for Array8)
-        bytes.write_u32_le(0);
+        write_hll_preamble(
+            &mut bytes,
+            lg_config_k,
+            HllType::Hll4,
+            cur_min,
+            num_at_cur_min,
+            aux_count as u32,
+            &estimation.estimator,
+        );
 
-        bytes.write(&self.bytes);
+        for pair in self.bytes.chunks_exact(2) {
+            let lo = (pair[0] - cur_min).min(AUX_TOKEN);
+            let hi = (pair[1] - cur_min).min(AUX_TOKEN);
+            bytes.write_u8(lo | (hi << 4));
+        }
+
+        if aux_count > 0 {
+            for (slot, &val) in self.bytes.iter().enumerate() {
+                if val - cur_min >= AUX_TOKEN {
+                    bytes.write_u32_le(Coupon::pack(slot as u32, val).raw());
+                }
+            }
+        }
 
         bytes.into_bytes()
     }
@@ -600,4 +662,93 @@ mod tests {
             );
         }
     }
+
+    #[test]
+    fn test_serialize_as_hll6_matches_array6_bytes() {
+        use crate::hll::HllSketch;
+
+        for lg_k in [4u8, 6, 8] {
+            let k = 1usize << lg_k;
+            let mut arr8 = Array8::new(lg_k);
+            let mut arr6 = crate::hll::array6::Array6::new(lg_k);
+            for slot in 0..k {
+                let val = ((slot * 7) % 64) as u8;
+                if val > 0 {
+                    let coupon = Coupon::pack(slot as u32, val);
+                    arr8.update(coupon);
+                    arr6.update(coupon);
+                }
+            }
+            assert_eq!(arr8.serialize_as(lg_k, HllType::Hll6), 
arr6.serialize(lg_k));
+
+            // Composite / out-of-order mode matches too.
+            arr8.invalidate_estimator();
+            arr6.restore_estimate_state(EstimateState::Composite);
+            assert_eq!(arr8.serialize_as(lg_k, HllType::Hll6), 
arr6.serialize(lg_k));
+
+            let decoded = HllSketch::deserialize(&arr8.serialize_as(lg_k, 
HllType::Hll6)).unwrap();
+            assert_eq!(decoded.estimate(), arr6.estimate());
+            assert_eq!(decoded.composite_estimate(), 
arr6.composite_estimate());
+        }
+    }
+
+    #[test]
+    fn test_serialize_as_hll4_handles_shifted_cur_min_and_multi_aux() {
+        use crate::hll::HllSketch;
+        use crate::hll::array4::Array4;
+
+        let lg_k = 4u8;
+        let k = 1usize << lg_k;
+        let mut arr8 = Array8::new(lg_k);
+        let mut arr4 = Array4::new(lg_k);
+
+        // Set cur_min = 5, boundary delta 14 (slot 2 -> 19), and three 
exceptions (slots 1, 7, 15).
+        let values = [5u8, 20, 19, 6, 5, 12, 8, 25, 9, 5, 18, 7, 11, 14, 15, 
63];
+        assert_eq!(values.len(), k);
+        for (slot, &val) in values.iter().enumerate() {
+            let coupon = Coupon::pack(slot as u32, val);
+            arr8.update(coupon);
+            arr4.update(coupon);
+        }
+
+        let direct_bytes = arr8.serialize_as(lg_k, HllType::Hll4);
+        assert_eq!(direct_bytes[6], 5); // cur_min == 5
+        assert_eq!(
+            u32::from_le_bytes(direct_bytes[36..40].try_into().unwrap()),
+            3
+        );
+
+        let decoded = HllSketch::deserialize(&direct_bytes).unwrap();
+        let expected = HllSketch::from_mode(lg_k, 
crate::hll::mode::Mode::Array4(arr4.clone()));
+        assert_eq!(decoded, expected);
+        assert_eq!(decoded.estimate(), expected.estimate());
+        assert_eq!(decoded.composite_estimate(), 
expected.composite_estimate());
+        for std_dev in [NumStdDev::One, NumStdDev::Two, NumStdDev::Three] {
+            assert_eq!(decoded.lower_bound(std_dev), 
expected.lower_bound(std_dev));
+            assert_eq!(decoded.upper_bound(std_dev), 
expected.upper_bound(std_dev));
+        }
+
+        // Composite / out-of-order state matches too.
+        arr8.invalidate_estimator();
+        arr4.restore_estimate_state(EstimateState::Composite);
+        let direct_ooo = arr8.serialize_as(lg_k, HllType::Hll4);
+        let decoded_ooo = HllSketch::deserialize(&direct_ooo).unwrap();
+        let expected_ooo = HllSketch::from_mode(lg_k, 
crate::hll::mode::Mode::Array4(arr4));
+        assert_eq!(decoded_ooo, expected_ooo);
+        assert_eq!(decoded_ooo.estimate(), expected_ooo.estimate());
+        assert_eq!(
+            decoded_ooo.composite_estimate(),
+            expected_ooo.composite_estimate()
+        );
+        for std_dev in [NumStdDev::One, NumStdDev::Two, NumStdDev::Three] {
+            assert_eq!(
+                decoded_ooo.lower_bound(std_dev),
+                expected_ooo.lower_bound(std_dev)
+            );
+            assert_eq!(
+                decoded_ooo.upper_bound(std_dev),
+                expected_ooo.upper_bound(std_dev)
+            );
+        }
+    }
 }
diff --git a/datasketches/src/hll/serialization.rs 
b/datasketches/src/hll/serialization.rs
index 166753e..c982aad 100644
--- a/datasketches/src/hll/serialization.rs
+++ b/datasketches/src/hll/serialization.rs
@@ -18,6 +18,11 @@
 //! HLL wire-format constants. Preamble lengths ending in `PREINTS` count 
32-bit words;
 //! those ending in `PREAMBLE_SIZE` count bytes.
 
+use crate::codec::SketchBytes;
+use crate::codec::family::Family;
+use crate::hll::HllType;
+use crate::hll::estimator::Estimator;
+
 pub const SERIAL_VERSION: u8 = 1;
 
 pub const EMPTY_FLAG_MASK: u8 = 4;
@@ -65,3 +70,40 @@ pub const TGT_HLL6: u8 = 1;
 pub const TGT_HLL8: u8 = 2;
 
 pub const COUPON_SIZE_BYTES: usize = 4;
+
+pub fn write_hll_preamble(
+    bytes: &mut SketchBytes,
+    lg_config_k: u8,
+    hll_type: HllType,
+    cur_min: u8,
+    num_at_cur_min: u32,
+    aux_count: u32,
+    estimator: &Estimator,
+) {
+    let (tgt_type, compact) = match hll_type {
+        HllType::Hll4 => (TGT_HLL4, true),
+        HllType::Hll6 => (TGT_HLL6, false),
+        HllType::Hll8 => (TGT_HLL8, false),
+    };
+
+    bytes.write_u8(HLL_PREINTS);
+    bytes.write_u8(SERIAL_VERSION);
+    bytes.write_u8(Family::HLL.id);
+    bytes.write_u8(lg_config_k);
+    bytes.write_u8(0); // unused in HLL6/HLL8 and compact HLL4
+
+    let mut flags = if compact { COMPACT_FLAG_MASK } else { 0 };
+    if estimator.uses_composite_estimate() {
+        flags |= OUT_OF_ORDER_FLAG_MASK;
+    }
+    bytes.write_u8(flags);
+    bytes.write_u8(cur_min);
+    bytes.write_u8(encode_mode_byte(CUR_MODE_HLL, tgt_type));
+
+    bytes.write_f64_le(estimator.hip_accum());
+    bytes.write_f64_le(estimator.kxq0());
+    bytes.write_f64_le(estimator.kxq1());
+
+    bytes.write_u32_le(num_at_cur_min);
+    bytes.write_u32_le(aux_count);
+}
diff --git a/datasketches/src/hll/union.rs b/datasketches/src/hll/union.rs
index 202e6f8..f5b9634 100644
--- a/datasketches/src/hll/union.rs
+++ b/datasketches/src/hll/union.rs
@@ -26,6 +26,7 @@ use crate::hll::HllType;
 use crate::hll::array4::Array4;
 use crate::hll::array6::Array6;
 use crate::hll::array8::Array8;
+use crate::hll::container::Container;
 use crate::hll::estimator::EstimateState;
 use crate::hll::mode::Mode;
 
@@ -129,37 +130,51 @@ impl HllUnion {
 
         let src_lg_k = sketch.lg_config_k();
         let dst_lg_k = self.gadget.lg_config_k();
-        let src_mode = sketch.mode();
 
-        match src_mode {
-            Mode::List { .. } | Mode::Set { .. } => {
-                self.update_from_list_or_set(sketch, src_mode, src_lg_k, 
dst_lg_k);
+        match sketch.mode() {
+            Mode::List { list, .. } => {
+                if self.gadget.is_empty() && src_lg_k == dst_lg_k {
+                    self.gadget = HllSketch::from_mode(
+                        src_lg_k,
+                        Mode::List {
+                            list: list.clone(),
+                            hll_type: HllType::Hll8,
+                        },
+                    );
+                } else {
+                    for coupon in list.container().iter() {
+                        self.gadget.update_with_coupon(coupon);
+                    }
+                }
             }
-            Mode::Array4(_) | Mode::Array6(_) | Mode::Array8(_) => {
-                self.update_from_array(src_mode, src_lg_k, dst_lg_k);
+            Mode::Set { set, .. } => {
+                if self.gadget.is_empty() && src_lg_k == dst_lg_k {
+                    self.gadget = HllSketch::from_mode(
+                        src_lg_k,
+                        Mode::Set {
+                            set: set.clone(),
+                            hll_type: HllType::Hll8,
+                        },
+                    );
+                } else {
+                    for coupon in set.container().iter() {
+                        self.gadget.update_with_coupon(coupon);
+                    }
+                }
+            }
+            Mode::Array4(src) => {
+                self.update_from_array(ArrayMode::Array4(src), src_lg_k, 
dst_lg_k);
+            }
+            Mode::Array6(src) => {
+                self.update_from_array(ArrayMode::Array6(src), src_lg_k, 
dst_lg_k);
+            }
+            Mode::Array8(src) => {
+                self.update_from_array(ArrayMode::Array8(src), src_lg_k, 
dst_lg_k);
             }
         }
     }
 
-    fn update_from_list_or_set(
-        &mut self,
-        sketch: &HllSketch,
-        src_mode: &Mode,
-        src_lg_k: u8,
-        dst_lg_k: u8,
-    ) {
-        if self.gadget.is_empty() && src_lg_k == dst_lg_k {
-            self.gadget = if sketch.target_type() == HllType::Hll8 {
-                sketch.clone()
-            } else {
-                convert_coupon_mode_to_hll8(src_mode, src_lg_k)
-            };
-        } else {
-            merge_coupons_into_gadget(&mut self.gadget, src_mode);
-        }
-    }
-
-    fn update_from_array(&mut self, src_mode: &Mode, src_lg_k: u8, dst_lg_k: 
u8) {
+    fn update_from_array(&mut self, src_mode: ArrayMode<'_>, src_lg_k: u8, 
dst_lg_k: u8) {
         if self.gadget.is_empty() {
             let new_array = copy_or_downsample(src_mode, src_lg_k, 
self.lg_max_k);
             let final_lg_k = new_array.num_registers().trailing_zeros() as u8;
@@ -167,52 +182,33 @@ impl HllUnion {
             return;
         }
 
-        let is_gadget_array = matches!(self.gadget.mode(), Mode::Array8(_));
-
-        if is_gadget_array {
-            self.merge_array_into_array_gadget(src_mode, src_lg_k, dst_lg_k);
-        } else {
-            self.promote_gadget_and_merge_array(src_mode, src_lg_k);
-        }
-    }
-
-    fn merge_array_into_array_gadget(&mut self, src_mode: &Mode, src_lg_k: u8, 
dst_lg_k: u8) {
-        if src_lg_k < dst_lg_k {
-            let mut new_array = Array8::new(src_lg_k);
-
-            match self.gadget.mode() {
-                Mode::Array8(old_gadget) => {
-                    new_array.merge_array_with_downsample(old_gadget.values(), 
dst_lg_k);
-                }
-                _ => {
-                    unreachable!("gadget mode changed unexpectedly; should 
never be Array4/Array6");
-                }
+        let lg_max_k = self.lg_max_k;
+        match self.gadget.mode_mut() {
+            Mode::List { list, .. } => {
+                let next =
+                    promote_coupons_and_merge_array(src_mode, src_lg_k, 
lg_max_k, list.container());
+                self.gadget = next;
             }
-
-            merge_array_same_lgk(&mut new_array, src_mode);
-            self.gadget = HllSketch::from_mode(src_lg_k, 
Mode::Array8(new_array));
-        } else {
-            match self.gadget.mode_mut() {
-                Mode::Array8(dst_array) => {
+            Mode::Set { set, .. } => {
+                let next =
+                    promote_coupons_and_merge_array(src_mode, src_lg_k, 
lg_max_k, set.container());
+                self.gadget = next;
+            }
+            Mode::Array8(dst_array) => {
+                if src_lg_k < dst_lg_k {
+                    let mut new_array = Array8::new(src_lg_k);
+                    new_array.merge_array_with_downsample(dst_array.values(), 
dst_lg_k);
+                    merge_array_same_lgk(&mut new_array, src_mode);
+                    self.gadget = HllSketch::from_mode(src_lg_k, 
Mode::Array8(new_array));
+                } else {
                     merge_array_into_array8(dst_array, dst_lg_k, src_mode, 
src_lg_k);
                 }
-                _ => {
-                    unreachable!("gadget mode changed unexpectedly; should 
never be Array4/Array6");
-                }
             }
+            Mode::Array4(_) => unreachable!("HllUnion gadget should never be 
in Array4 mode"),
+            Mode::Array6(_) => unreachable!("HllUnion gadget should never be 
in Array6 mode"),
         }
     }
 
-    fn promote_gadget_and_merge_array(&mut self, src_mode: &Mode, src_lg_k: 
u8) {
-        let mut new_array = copy_or_downsample(src_mode, src_lg_k, 
self.lg_max_k);
-
-        let old_gadget_mode = self.gadget.mode();
-        merge_coupons_into_mode(&mut new_array, old_gadget_mode);
-
-        let final_lg_k = new_array.num_registers().trailing_zeros() as u8;
-        self.gadget = HllSketch::from_mode(final_lg_k, 
Mode::Array8(new_array));
-    }
-
     /// Returns an independent sketch with the requested [`HllType`].
     ///
     /// The result retains the union's effective `lg_k` and cardinality 
estimate.
@@ -254,33 +250,46 @@ impl HllUnion {
             Mode::Array8(array8) => {
                 convert_array8_to_type(array8, self.gadget.lg_config_k(), 
hll_type)
             }
-            Mode::Array4(_) | Mode::Array6(_) => {
-                unreachable!("gadget mode changed unexpectedly; should never 
be Array4/Array6")
-            }
+            Mode::Array4(_) => unreachable!("HllUnion gadget should never be 
in Array4 mode"),
+            Mode::Array6(_) => unreachable!("HllUnion gadget should never be 
in Array6 mode"),
         }
     }
 
-    /// Serializes the union's result as an [`HllType::Hll8`] sketch.
+    /// Serializes the union's result as an [`HllSketch`] with the requested 
[`HllType`].
     ///
-    /// Produces the same bytes as `to_sketch(HllType::Hll8).serialize()` 
without copying an
-    /// intermediate sketch. The image retains the effective `lg_k` and 
estimate, but not the
-    /// union's configured maximum `lg_k`. It can be read with 
[`HllSketch::deserialize`].
+    /// Produces an equivalent sketch to [`Self::to_sketch`] followed by 
[`HllSketch::serialize`]
+    /// without allocating or cloning an intermediate sketch. For 
[`HllType::Hll6`],
+    /// [`HllType::Hll8`], coupon modes, and [`HllType::Hll4`] with at most 
one auxiliary entry,
+    /// the output matches `to_sketch(hll_type).serialize()` byte-for-byte; 
for [`HllType::Hll4`]
+    /// with multiple auxiliary entries, auxiliary entries are written in 
ascending slot order
+    /// rather than hash-table order.
+    ///
+    /// The image retains the effective `lg_k` and estimate, but not the 
union's configured maximum
+    /// `lg_k`. It can be read with [`HllSketch::deserialize`].
     ///
     /// # Examples
     ///
     /// ```
     /// use datasketches::hll::HllSketch;
+    /// use datasketches::hll::HllType;
     /// use datasketches::hll::HllUnion;
     ///
     /// let mut union = HllUnion::new(12).unwrap();
     /// union.update_value("apple");
-    /// let mut partial = HllSketch::deserialize(&union.serialize()).unwrap();
+    /// let mut partial = 
HllSketch::deserialize(&union.serialize(HllType::Hll8)).unwrap();
     /// partial.update("banana");
     /// union.update(&partial);
     /// assert!((union.estimate() - 2.0).abs() < 0.01);
     /// ```
-    pub fn serialize(&self) -> Vec<u8> {
-        self.gadget.serialize()
+    pub fn serialize(&self, hll_type: HllType) -> Vec<u8> {
+        let lg_config_k = self.gadget.lg_config_k();
+        match self.gadget.mode() {
+            Mode::List { list, .. } => list.serialize(lg_config_k, hll_type),
+            Mode::Set { set, .. } => set.serialize(lg_config_k, hll_type),
+            Mode::Array8(arr) => arr.serialize_as(lg_config_k, hll_type),
+            Mode::Array4(_) => unreachable!("HllUnion gadget should never be 
in Array4 mode"),
+            Mode::Array6(_) => unreachable!("HllUnion gadget should never be 
in Array6 mode"),
+        }
     }
 
     /// Returns the union's current effective `lg_k`.
@@ -405,68 +414,44 @@ impl HllUnion {
     }
 }
 
-fn convert_coupon_mode_to_hll8(src_mode: &Mode, src_lg_k: u8) -> HllSketch {
-    match src_mode {
-        Mode::List { list, .. } => HllSketch::from_mode(
-            src_lg_k,
-            Mode::List {
-                list: list.clone(),
-                hll_type: HllType::Hll8,
-            },
-        ),
-        Mode::Set { set, .. } => HllSketch::from_mode(
-            src_lg_k,
-            Mode::Set {
-                set: set.clone(),
-                hll_type: HllType::Hll8,
-            },
-        ),
-        _ => unreachable!("convert_coupon_mode_to_hll8 called with non-coupon 
mode"),
-    }
+#[derive(Clone, Copy)]
+enum ArrayMode<'a> {
+    Array4(&'a Array4),
+    Array6(&'a Array6),
+    Array8(&'a Array8),
 }
 
-fn merge_coupons_into_gadget(gadget: &mut HllSketch, src_mode: &Mode) {
-    match src_mode {
-        Mode::List { list, .. } => {
-            for coupon in list.container().iter() {
-                gadget.update_with_coupon(coupon);
-            }
-        }
-        Mode::Set { set, .. } => {
-            for coupon in set.container().iter() {
-                gadget.update_with_coupon(coupon);
-            }
-        }
-        Mode::Array4(_) | Mode::Array6(_) | Mode::Array8(_) => {
-            unreachable!(
-                "merge_coupons_into_gadget called with array mode; array modes 
should use merge_array_into_array8"
-            );
+impl ArrayMode<'_> {
+    fn estimate_state(self) -> EstimateState {
+        match self {
+            Self::Array4(src) => src.estimate_state(),
+            Self::Array6(src) => src.estimate_state(),
+            Self::Array8(src) => src.estimate_state(),
         }
     }
 }
 
-fn merge_coupons_into_mode(dst: &mut Array8, src_mode: &Mode) {
-    match src_mode {
-        Mode::List { list, .. } => {
-            for coupon in list.container().iter() {
-                dst.update(coupon);
-            }
-        }
-        Mode::Set { set, .. } => {
-            for coupon in set.container().iter() {
-                dst.update(coupon);
-            }
-        }
-        Mode::Array4(_) | Mode::Array6(_) | Mode::Array8(_) => {
-            unreachable!(
-                "merge_coupons_into_mode called with array mode; array modes 
should use copy_or_downsample"
-            );
-        }
+fn promote_coupons_and_merge_array(
+    src_mode: ArrayMode<'_>,
+    src_lg_k: u8,
+    lg_max_k: u8,
+    coupons: &Container,
+) -> HllSketch {
+    let mut new_array = copy_or_downsample(src_mode, src_lg_k, lg_max_k);
+    for coupon in coupons.iter() {
+        new_array.update(coupon);
     }
+    let final_lg_k = new_array.num_registers().trailing_zeros() as u8;
+    HllSketch::from_mode(final_lg_k, Mode::Array8(new_array))
 }
 
 /// The caller must downsize the destination first if the source has a smaller 
`lg_k`.
-fn merge_array_into_array8(dst_array8: &mut Array8, dst_lg_k: u8, src_mode: 
&Mode, src_lg_k: u8) {
+fn merge_array_into_array8(
+    dst_array8: &mut Array8,
+    dst_lg_k: u8,
+    src_mode: ArrayMode<'_>,
+    src_lg_k: u8,
+) {
     assert!(
         src_lg_k >= dst_lg_k,
         "merge_array_into_array8 requires src_lg_k >= dst_lg_k (got src={}, 
dst={})",
@@ -481,19 +466,6 @@ fn merge_array_into_array8(dst_array8: &mut Array8, 
dst_lg_k: u8, src_mode: &Mod
     }
 }
 
-fn get_array_estimate_state(mode: &Mode) -> EstimateState {
-    match mode {
-        Mode::Array8(src) => src.estimate_state(),
-        Mode::Array6(src) => src.estimate_state(),
-        Mode::Array4(src) => src.estimate_state(),
-        Mode::List { .. } | Mode::Set { .. } => {
-            unreachable!(
-                "get_array_estimate_state called with non-array mode; List/Set 
not supported"
-            );
-        }
-    }
-}
-
 fn merge_array46_same_lgk(dst: &mut Array8, num_registers: usize, get_value: 
impl Fn(u32) -> u8) {
     for slot in 0..num_registers {
         let val = get_value(slot as u32);
@@ -506,20 +478,17 @@ fn merge_array46_same_lgk(dst: &mut Array8, 
num_registers: usize, get_value: imp
 }
 
 /// Merging independent register histories invalidates the HIP accumulator.
-fn merge_array_same_lgk(dst: &mut Array8, src_mode: &Mode) {
+fn merge_array_same_lgk(dst: &mut Array8, src_mode: ArrayMode<'_>) {
     match src_mode {
-        Mode::Array8(src) => {
+        ArrayMode::Array8(src) => {
             dst.merge_array_same_lgk(src.values());
         }
-        Mode::Array6(src) => {
+        ArrayMode::Array6(src) => {
             merge_array46_same_lgk(dst, src.num_registers(), |slot| 
src.get(slot));
         }
-        Mode::Array4(src) => {
+        ArrayMode::Array4(src) => {
             merge_array46_same_lgk(dst, src.num_registers(), |slot| 
src.get(slot));
         }
-        _ => {
-            unreachable!("merge_array_same_lgk called with non-array mode; 
List/Set not supported")
-        }
     }
 }
 
@@ -545,7 +514,12 @@ fn merge_array46_with_downsample(
 
 /// Multiple source registers map to each destination register via masking.
 /// Merging independent register histories invalidates the HIP accumulator.
-fn merge_array_with_downsample(dst: &mut Array8, dst_lg_k: u8, src_mode: 
&Mode, src_lg_k: u8) {
+fn merge_array_with_downsample(
+    dst: &mut Array8,
+    dst_lg_k: u8,
+    src_mode: ArrayMode<'_>,
+    src_lg_k: u8,
+) {
     assert!(
         src_lg_k > dst_lg_k,
         "merge_array_with_downsample requires src_lg_k > dst_lg_k (got src={}, 
dst={})",
@@ -554,18 +528,15 @@ fn merge_array_with_downsample(dst: &mut Array8, 
dst_lg_k: u8, src_mode: &Mode,
     );
 
     match src_mode {
-        Mode::Array8(src) => {
+        ArrayMode::Array8(src) => {
             dst.merge_array_with_downsample(src.values(), src_lg_k);
         }
-        Mode::Array6(src) => {
+        ArrayMode::Array6(src) => {
             merge_array46_with_downsample(dst, dst_lg_k, src.num_registers(), 
|slot| src.get(slot));
         }
-        Mode::Array4(src) => {
+        ArrayMode::Array4(src) => {
             merge_array46_with_downsample(dst, dst_lg_k, src.num_registers(), 
|slot| src.get(slot));
         }
-        _ => unreachable!(
-            "merge_array_with_downsample called with non-array mode; List/Set 
not supported"
-        ),
     }
 }
 
@@ -616,27 +587,22 @@ fn copy_array46_via_coupons(dst: &mut Array8, 
num_registers: usize, get_value: i
 }
 
 /// Preserves the source estimate state because the result represents the same 
logical sketch.
-fn copy_or_downsample(src_mode: &Mode, src_lg_k: u8, tgt_lg_k: u8) -> Array8 {
-    let state = get_array_estimate_state(src_mode);
+fn copy_or_downsample(src_mode: ArrayMode<'_>, src_lg_k: u8, tgt_lg_k: u8) -> 
Array8 {
+    let state = src_mode.estimate_state();
 
     let mut result = if src_lg_k <= tgt_lg_k {
         match src_mode {
-            Mode::Array8(src) => src.clone(),
-            Mode::Array6(src) => {
+            ArrayMode::Array8(src) => src.clone(),
+            ArrayMode::Array6(src) => {
                 let mut result = Array8::new(src_lg_k);
                 copy_array46_via_coupons(&mut result, src.num_registers(), 
|slot| src.get(slot));
                 result
             }
-            Mode::Array4(src) => {
+            ArrayMode::Array4(src) => {
                 let mut result = Array8::new(src_lg_k);
                 copy_array46_via_coupons(&mut result, src.num_registers(), 
|slot| src.get(slot));
                 result
             }
-            Mode::List { .. } | Mode::Set { .. } => {
-                unreachable!(
-                    "copy_or_downsample called with non-array mode; List/Set 
not supported"
-                );
-            }
         }
     } else {
         let mut result = Array8::new(tgt_lg_k);
diff --git a/datasketches/src/thetafamily/theta/serialization.rs 
b/datasketches/src/thetafamily/theta/serialization.rs
index a36c5bd..8ff151a 100644
--- a/datasketches/src/thetafamily/theta/serialization.rs
+++ b/datasketches/src/thetafamily/theta/serialization.rs
@@ -73,3 +73,93 @@ pub(super) fn serialize_compact_uncompressed<E: SketchEntry>(
     }
     bytes.into_bytes()
 }
+
+pub(super) fn serialize_compact_compressed<E: SketchEntry>(
+    state: &CompactSketchState<E>,
+) -> Vec<u8> {
+    if is_suitable_for_compression(state) {
+        serialize_v4(state)
+    } else {
+        serialize_compact_uncompressed(state)
+    }
+}
+
+fn is_suitable_for_compression<E: SketchEntry>(state: &CompactSketchState<E>) 
-> bool {
+    let num_retained = state.retained_entries().len();
+    state.is_ordered() && num_retained != 0 && (num_retained != 1 || 
state.is_estimation_mode())
+}
+
+fn serialize_v4<E: SketchEntry>(state: &CompactSketchState<E>) -> Vec<u8> {
+    let entries = state.retained_entries();
+    let pre_longs = if state.is_estimation_mode() { 2u8 } else { 1u8 };
+    let entry_bits = compute_entry_bits(entries);
+    let num_entries_bytes = num_entries_bytes(entries.len());
+
+    // Pre-size exactly: preamble longs (8 bytes each) + num_entries_bytes + 
packed bits.
+    let compressed_bits = entry_bits as usize * entries.len();
+    let compressed_bytes = compressed_bits.div_ceil(8);
+    let out_bytes = (pre_longs as usize * 8) + (num_entries_bytes as usize) + 
compressed_bytes;
+    let mut bytes = SketchBytes::with_capacity(out_bytes);
+
+    bytes.write_u8(pre_longs);
+    bytes.write_u8(COMPRESSED_SERIAL_VERSION);
+    bytes.write_u8(Family::THETA.id);
+    bytes.write_u8(entry_bits);
+    bytes.write_u8(num_entries_bytes);
+
+    let mut flags = 0u8;
+    flags |= FLAGS_IS_READ_ONLY;
+    flags |= FLAGS_IS_COMPACT;
+    flags |= FLAGS_IS_ORDERED;
+    bytes.write_u8(flags);
+
+    bytes.write_u16_le(state.seed_hash());
+    if state.is_estimation_mode() {
+        bytes.write_u64_le(state.theta());
+    }
+
+    let mut n = entries.len() as u32;
+    for _ in 0..num_entries_bytes {
+        bytes.write_u8((n & 0xff) as u8);
+        n >>= 8;
+    }
+
+    let bits = u32::from(entry_bits);
+    let mut acc = 0u128;
+    let mut acc_bits = 0u32;
+    let mut previous = 0u64;
+    for entry in entries {
+        let hash = entry.hash();
+        acc = (acc << bits) | u128::from(hash - previous);
+        previous = hash;
+        acc_bits += bits;
+        if acc_bits >= 64 {
+            acc_bits -= 64;
+            bytes.write(&((acc >> acc_bits) as u64).to_be_bytes());
+        }
+    }
+    if acc_bits > 0 {
+        let tail = ((acc << (64 - acc_bits)) as u64).to_be_bytes();
+        bytes.write(&tail[..acc_bits.div_ceil(8) as usize]);
+    }
+
+    bytes.into_bytes()
+}
+
+fn compute_entry_bits<E: SketchEntry>(entries: &[E]) -> u8 {
+    let mut previous = 0u64;
+    let mut ored = 0u64;
+    for entry in entries {
+        let hash = entry.hash();
+        let delta = hash - previous;
+        ored |= delta;
+        previous = hash;
+    }
+    (64 - ored.leading_zeros()) as u8
+}
+
+fn num_entries_bytes(num_entries: usize) -> u8 {
+    let n = num_entries as u32;
+    let bits = u32::BITS - n.leading_zeros();
+    bits.div_ceil(8) as u8
+}
diff --git a/datasketches/src/thetafamily/theta/sketch.rs 
b/datasketches/src/thetafamily/theta/sketch.rs
index 3088406..c8a43ab 100644
--- a/datasketches/src/thetafamily/theta/sketch.rs
+++ b/datasketches/src/thetafamily/theta/sketch.rs
@@ -25,7 +25,6 @@ use std::hash::Hash;
 use std::iter::FusedIterator;
 use std::slice;
 
-use crate::codec::SketchBytes;
 use crate::codec::SketchSlice;
 use crate::codec::assert::ensure_preamble_longs_in_range;
 use crate::codec::assert::insufficient_data;
@@ -48,10 +47,8 @@ use crate::thetafamily::common::KeySketch;
 use crate::thetafamily::common::SketchEntry;
 use crate::thetafamily::common::binomial_bounds;
 use crate::thetafamily::common::constants::DEFAULT_LG_K;
-use crate::thetafamily::common::constants::FLAGS_IS_COMPACT;
 use crate::thetafamily::common::constants::FLAGS_IS_EMPTY;
 use crate::thetafamily::common::constants::FLAGS_IS_ORDERED;
-use crate::thetafamily::common::constants::FLAGS_IS_READ_ONLY;
 use crate::thetafamily::common::constants::MAX_THETA;
 use crate::thetafamily::common::hash_table::SketchHashTable;
 use crate::thetafamily::common::hash_table::SketchHashTableIter;
@@ -591,17 +588,7 @@ impl CompactThetaSketch {
     ///
     /// Falls back to [`serialize`](Self::serialize) when compression is not 
applicable.
     pub fn serialize_compressed(&self) -> Vec<u8> {
-        if self.is_suitable_for_compression() {
-            self.serialize_v4()
-        } else {
-            self.serialize()
-        }
-    }
-
-    fn is_suitable_for_compression(&self) -> bool {
-        self.is_ordered()
-            && self.num_retained() != 0
-            && (self.num_retained() != 1 || self.is_estimation_mode())
+        serialization::serialize_compact_compressed(&self.compact_state)
     }
 
     /// Serializes this sketch into the uncompressed compact Theta format.
@@ -613,79 +600,6 @@ impl CompactThetaSketch {
         serialization::serialize_compact_uncompressed(&self.compact_state)
     }
 
-    fn serialize_v4(&self) -> Vec<u8> {
-        let retained_hashes = self.retained_hashes();
-        let pre_longs = if self.is_estimation_mode() { 2u8 } else { 1u8 };
-        let entry_bits = Self::compute_entry_bits(retained_hashes);
-        let num_entries_bytes = Self::num_entries_bytes(retained_hashes.len());
-
-        // Pre-size exactly: preamble longs (8 bytes each) + num_entries_bytes 
+ packed bits.
-        let compressed_bits = entry_bits as usize * retained_hashes.len();
-        let compressed_bytes = compressed_bits.div_ceil(8);
-        let out_bytes = (pre_longs as usize * 8) + (num_entries_bytes as 
usize) + compressed_bytes;
-        let mut bytes = SketchBytes::with_capacity(out_bytes);
-
-        bytes.write_u8(pre_longs);
-        bytes.write_u8(serialization::COMPRESSED_SERIAL_VERSION);
-        bytes.write_u8(Family::THETA.id);
-        bytes.write_u8(entry_bits);
-        bytes.write_u8(num_entries_bytes);
-
-        let mut flags = 0u8;
-        flags |= FLAGS_IS_READ_ONLY;
-        flags |= FLAGS_IS_COMPACT;
-        flags |= FLAGS_IS_ORDERED;
-        bytes.write_u8(flags);
-
-        bytes.write_u16_le(self.seed_hash());
-        if self.is_estimation_mode() {
-            bytes.write_u64_le(self.theta64());
-        }
-
-        let mut n = retained_hashes.len() as u32;
-        for _ in 0..num_entries_bytes {
-            bytes.write_u8((n & 0xff) as u8);
-            n >>= 8;
-        }
-
-        let bits = u32::from(entry_bits);
-        let mut acc = 0u128;
-        let mut acc_bits = 0u32;
-        let mut previous = 0u64;
-        for &entry in retained_hashes {
-            acc = (acc << bits) | u128::from(entry - previous);
-            previous = entry;
-            acc_bits += bits;
-            if acc_bits >= 64 {
-                acc_bits -= 64;
-                bytes.write(&((acc >> acc_bits) as u64).to_be_bytes());
-            }
-        }
-        if acc_bits > 0 {
-            let tail = ((acc << (64 - acc_bits)) as u64).to_be_bytes();
-            bytes.write(&tail[..acc_bits.div_ceil(8) as usize]);
-        }
-
-        bytes.into_bytes()
-    }
-
-    fn compute_entry_bits(entries: &[u64]) -> u8 {
-        let mut previous = 0u64;
-        let mut ored = 0u64;
-        for &entry in entries {
-            let delta = entry - previous;
-            ored |= delta;
-            previous = entry;
-        }
-        (64 - ored.leading_zeros()) as u8
-    }
-
-    fn num_entries_bytes(num_entries: usize) -> u8 {
-        let n = num_entries as u32;
-        let bits = u32::BITS - n.leading_zeros();
-        bits.div_ceil(8) as u8
-    }
-
     /// Deserializes a compact Theta sketch using the default seed.
     ///
     /// Also accepts data serialized by other DataSketches implementations.
diff --git a/datasketches/src/thetafamily/theta/union.rs 
b/datasketches/src/thetafamily/theta/union.rs
index ecac475..efd9187 100644
--- a/datasketches/src/thetafamily/theta/union.rs
+++ b/datasketches/src/thetafamily/theta/union.rs
@@ -65,14 +65,50 @@ impl ThetaUnion {
 
     /// Serializes this union result into the uncompressed compact Theta 
format.
     ///
-    /// Produces the same bytes as `self.to_sketch(ordered).serialize()`. When 
`ordered` is `true`,
-    /// retained hashes are sorted. Otherwise they may be unordered; empty 
results and exact
-    /// singletons always use their canonical encoding.
+    /// The result is the same as [`Self::to_sketch`] followed by
+    /// [`CompactThetaSketch::serialize`]: the same retained hashes, theta, 
and seed hash, and
+    /// identical bytes when `ordered` is `true` 
(`to_sketch(true).serialize()`). When `ordered` is
+    /// `false`, retained hashes may appear in a different order. Empty 
results and exact singletons
+    /// always use their canonical encoding.
     pub fn serialize(&self, ordered: bool) -> Vec<u8> {
         let state = self.state.to_compact_hash_state(ordered);
         serialization::serialize_compact_uncompressed(&state)
     }
 
+    /// Serializes this union result in compressed compact Theta format if 
applicable.
+    ///
+    /// Produces the same bytes as 
`self.to_sketch(true).serialize_compressed()`. Compressed
+    /// serialization requires ordered entries, so retained hashes are sorted 
ascending. Falls back
+    /// to uncompressed canonical encoding for empty sketches, zero-entry 
estimation sketches, and
+    /// exact singletons.
+    ///
+    /// The serialized data can be read by other DataSketches implementations 
via
+    /// [`CompactThetaSketch::deserialize`] or 
[`CompactThetaSketch::deserialize_with_seed`].
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use datasketches::theta::CompactThetaSketch;
+    /// use datasketches::theta::ThetaSketchBuilder;
+    /// use datasketches::theta::ThetaUnionBuilder;
+    ///
+    /// let mut sketch = 
ThetaSketchBuilder::default().lg_k(12).build().unwrap();
+    /// for value in 0..100 {
+    ///     sketch.update(value);
+    /// }
+    ///
+    /// let mut union = ThetaUnionBuilder::default().lg_k(12).build().unwrap();
+    /// union.update(&sketch).unwrap();
+    ///
+    /// let bytes = union.serialize_compressed();
+    /// let restored = CompactThetaSketch::deserialize(&bytes).unwrap();
+    /// assert_eq!(restored.num_retained(), 100);
+    /// ```
+    pub fn serialize_compressed(&self) -> Vec<u8> {
+        let state = self.state.to_compact_hash_state(true);
+        serialization::serialize_compact_compressed(&state)
+    }
+
     /// Resets the union to its empty state.
     pub fn reset(&mut self) {
         self.state.reset();
diff --git a/tests-integration/tests/hll_test/union.rs 
b/tests-integration/tests/hll_test/union.rs
index e02f240..56c4e44 100644
--- a/tests-integration/tests/hll_test/union.rs
+++ b/tests-integration/tests/hll_test/union.rs
@@ -784,7 +784,7 @@ fn test_union_query_timing_does_not_change_mixed_updates() {
             &queried.to_sketch(HllType::Hll8),
             &queried.to_sketch(HllType::Hll4),
         );
-        let restored = HllSketch::deserialize(&queried.serialize()).unwrap();
+        let restored = 
HllSketch::deserialize(&queried.serialize(HllType::Hll8)).unwrap();
         assert_eq!(restored.composite_estimate(), 
queried.composite_estimate());
         for value in start + 5_000..start + 5_100 {
             queried.update_value(value);
@@ -792,7 +792,10 @@ fn test_union_query_timing_does_not_change_mixed_updates() 
{
         }
     }
 
-    assert_eq!(queried.serialize(), deferred.serialize());
+    assert_eq!(
+        queried.serialize(HllType::Hll8),
+        deferred.serialize(HllType::Hll8)
+    );
     assert_same_estimate_and_bounds(
         &queried.to_sketch(HllType::Hll8),
         &deferred.to_sketch(HllType::Hll8),
@@ -808,7 +811,10 @@ fn test_union_query_timing_does_not_change_mixed_updates() 
{
         copied.update_value(value);
         deferred.update_value(value);
     }
-    assert_eq!(copied.serialize(), deferred.serialize());
+    assert_eq!(
+        copied.serialize(HllType::Hll8),
+        deferred.serialize(HllType::Hll8)
+    );
 }
 
 #[test]
@@ -822,25 +828,36 @@ fn 
test_union_supports_shared_queries_after_dense_merges() {
             (index + 1) * 5_000,
         ));
     }
-    let expected = union.to_sketch(HllType::Hll8);
-    let bytes = expected.serialize();
+    let expected_hll8 = union.to_sketch(HllType::Hll8);
+    let bytes_hll8 = expected_hll8.serialize();
+    let expected_hll6 = union.to_sketch(HllType::Hll6);
+    let bytes_hll6 = expected_hll6.serialize();
+    let expected_hll4 = union.to_sketch(HllType::Hll4);
     let barrier = std::sync::Barrier::new(4);
 
     std::thread::scope(|scope| {
         for _ in 0..4 {
             scope.spawn(|| {
                 barrier.wait();
-                assert_eq!(union.estimate(), expected.estimate());
-                assert_eq!(union.composite_estimate(), 
expected.composite_estimate());
+                assert_eq!(union.estimate(), expected_hll8.estimate());
+                assert_eq!(
+                    union.composite_estimate(),
+                    expected_hll8.composite_estimate()
+                );
                 assert_eq!(
                     union.lower_bound(NumStdDev::Two),
-                    expected.lower_bound(NumStdDev::Two)
+                    expected_hll8.lower_bound(NumStdDev::Two)
                 );
                 assert_eq!(
                     union.upper_bound(NumStdDev::Two),
-                    expected.upper_bound(NumStdDev::Two)
+                    expected_hll8.upper_bound(NumStdDev::Two)
+                );
+                assert_eq!(union.serialize(HllType::Hll8), bytes_hll8);
+                assert_eq!(union.serialize(HllType::Hll6), bytes_hll6);
+                assert_eq!(
+                    
HllSketch::deserialize(&union.serialize(HllType::Hll4)).unwrap(),
+                    expected_hll4
                 );
-                assert_eq!(union.serialize(), bytes);
             });
         }
     });
diff --git a/tests-integration/tests/serde_tests/hll.rs 
b/tests-integration/tests/serde_tests/hll.rs
index ed0dd41..8aed0b1 100644
--- a/tests-integration/tests/serde_tests/hll.rs
+++ b/tests-integration/tests/serde_tests/hll.rs
@@ -18,6 +18,7 @@
 use std::fs;
 use std::path::PathBuf;
 
+use datasketches::common::NumStdDev;
 use datasketches::hash::value::natural_extend;
 use datasketches::hll::HllSketch;
 use datasketches::hll::HllType;
@@ -42,7 +43,7 @@ fn 
union_serialization_preserves_result_and_subsequent_updates() {
             for lg_max_k in [8, 12, 14] {
                 let mut union = HllUnion::new(lg_max_k).unwrap();
                 union.update(&source);
-                let bytes = union.serialize();
+                let bytes = union.serialize(HllType::Hll8);
                 assert_eq!(bytes, union.to_sketch(HllType::Hll8).serialize());
 
                 let mut restored = HllSketch::deserialize(&bytes).unwrap();
@@ -57,10 +58,177 @@ fn 
union_serialization_preserves_result_and_subsequent_updates() {
                 assert_eq!(union.to_sketch(HllType::Hll8), restored);
 
                 union.reset();
-                let empty = 
HllSketch::deserialize(&union.serialize()).unwrap();
-                assert!(empty.is_empty());
-                assert_eq!(empty.lg_config_k(), lg_max_k);
+                for target_type in [HllType::Hll4, HllType::Hll6, 
HllType::Hll8] {
+                    let empty = 
HllSketch::deserialize(&union.serialize(target_type)).unwrap();
+                    assert!(empty.is_empty());
+                    assert_eq!(empty.target_type(), target_type);
+                    assert_eq!(empty.lg_config_k(), lg_max_k);
+                }
+            }
+        }
+    }
+}
+
+fn assert_union_matches_sketch(
+    union: &HllUnion,
+    target_type: HllType,
+    check_bytes_when_single_aux: bool,
+) {
+    let bytes = union.serialize(target_type);
+    let expected = union.to_sketch(target_type);
+    if check_bytes_when_single_aux {
+        let dense_offset = 40 + (1usize << (union.lg_config_k() - 1));
+        let single_or_no_aux =
+            target_type != HllType::Hll4 || bytes.len() <= dense_offset + 
size_of::<u32>();
+        if single_or_no_aux {
+            assert_eq!(
+                bytes,
+                expected.serialize(),
+                "byte mismatch for target_type={target_type:?}, lg_k={}",
+                union.lg_config_k()
+            );
+        }
+    }
+
+    let restored = HllSketch::deserialize(&bytes).unwrap();
+    assert_eq!(restored.target_type(), target_type);
+    assert_eq!(restored.lg_config_k(), expected.lg_config_k());
+    assert_eq!(restored.is_empty(), expected.is_empty());
+    assert_eq!(restored, expected);
+    assert_eq!(restored.estimate(), expected.estimate());
+    assert_eq!(restored.composite_estimate(), expected.composite_estimate());
+    assert_eq!(restored.estimate(), union.estimate());
+    assert_eq!(restored.composite_estimate(), union.composite_estimate());
+    for num_std_dev in [NumStdDev::One, NumStdDev::Two, NumStdDev::Three] {
+        assert_eq!(
+            restored.lower_bound(num_std_dev),
+            expected.lower_bound(num_std_dev)
+        );
+        assert_eq!(
+            restored.upper_bound(num_std_dev),
+            expected.upper_bound(num_std_dev)
+        );
+        assert_eq!(
+            restored.lower_bound(num_std_dev),
+            union.lower_bound(num_std_dev)
+        );
+        assert_eq!(
+            restored.upper_bound(num_std_dev),
+            union.upper_bound(num_std_dev)
+        );
+    }
+}
+
+#[test]
+fn union_serialization_handles_all_modes_and_target_types() {
+    for count in [0, 4, 100, 10_000_u64] {
+        let mut union = HllUnion::new(12).unwrap();
+        for value in 0..count {
+            union.update_value(value);
+        }
+        for target_type in [HllType::Hll4, HllType::Hll6, HllType::Hll8] {
+            assert_union_matches_sketch(&union, target_type, true);
+        }
+    }
+}
+
+#[test]
+fn union_serialization_cold_and_warm_composite_states_match() {
+    let build_composite_union = || {
+        let mut union = HllUnion::new(12).unwrap();
+        for (start, end) in [(0_u64, 3_000), (3_000, 6_000)] {
+            let mut sketch = HllSketch::new(12, HllType::Hll8).unwrap();
+            for value in start..end {
+                sketch.update(value);
             }
+            union.update(&sketch);
+        }
+        union
+    };
+
+    for target_type in [HllType::Hll4, HllType::Hll6, HllType::Hll8] {
+        // Cold: serialize before calling any estimate or to_sketch on this 
union.
+        let cold_union = build_composite_union();
+        let cold_bytes = cold_union.serialize(target_type);
+
+        // Warm: populate lazy estimator cache before serializing.
+        let warm_union = build_composite_union();
+        let _ = warm_union.composite_estimate();
+        let warm_bytes = warm_union.serialize(target_type);
+
+        assert_eq!(cold_bytes, warm_bytes);
+        assert_union_matches_sketch(&cold_union, target_type, true);
+    }
+}
+
+#[test]
+fn union_serialization_handles_downsampled_unions() {
+    // Single-sketch downsample keeps HIP mode.
+    let mut wide = HllSketch::new(14, HllType::Hll8).unwrap();
+    for value in 0..10_000_u64 {
+        wide.update(value);
+    }
+    let mut hip_downsampled = HllUnion::new(10).unwrap();
+    hip_downsampled.update(&wide);
+    assert_eq!(hip_downsampled.lg_config_k(), 10);
+    for target_type in [HllType::Hll4, HllType::Hll6, HllType::Hll8] {
+        assert_union_matches_sketch(&hip_downsampled, target_type, true);
+    }
+
+    // Multi-sketch downsample merges into dense OOO Array8 at the smaller 
lg_k.
+    let mut narrow = HllSketch::new(8, HllType::Hll4).unwrap();
+    for value in 10_000..15_000_u64 {
+        narrow.update(value);
+    }
+    let mut ooo_downsampled = HllUnion::new(12).unwrap();
+    ooo_downsampled.update(&wide);
+    ooo_downsampled.update(&narrow);
+    assert_eq!(ooo_downsampled.lg_config_k(), 8);
+    for target_type in [HllType::Hll4, HllType::Hll6, HllType::Hll8] {
+        assert_union_matches_sketch(&ooo_downsampled, target_type, true);
+    }
+}
+
+#[test]
+fn union_serialization_hll4_handles_shifted_cur_min_and_multi_aux() {
+    // Keys verified at lg_k = 4 to hit distinct slots with register value >= 
22.
+    const HIGH_VALUE_KEYS: [u64; 4] = [503_824, 2_048_382, 2_144_141, 
9_410_086];
+
+    let mut direct_union = HllUnion::new(4).unwrap();
+    for value in 0..200_u64 {
+        direct_union.update_value(value);
+    }
+    for value in HIGH_VALUE_KEYS {
+        direct_union.update_value(value);
+    }
+
+    let mut merged_left = HllSketch::new(4, HllType::Hll8).unwrap();
+    for value in 0..200_u64 {
+        merged_left.update(value);
+    }
+    let mut merged_right = HllSketch::new(4, HllType::Hll8).unwrap();
+    for value in HIGH_VALUE_KEYS {
+        merged_right.update(value);
+    }
+    let mut merged_union = HllUnion::new(4).unwrap();
+    merged_union.update(&merged_left);
+    merged_union.update(&merged_right);
+
+    for union in [&direct_union, &merged_union] {
+        let hll4_bytes = union.serialize(HllType::Hll4);
+        let expected_hll4_bytes = union.to_sketch(HllType::Hll4).serialize();
+        let dense_end = 40 + (1usize << (4 - 1));
+        assert!(hll4_bytes[6] > 0, "expected shifted cur_min > 0");
+        assert!(
+            (hll4_bytes.len() - dense_end) / size_of::<u32>() >= 2,
+            "expected at least 2 aux exceptions"
+        );
+        // Preamble and packed nibbles must match bit-for-bit; only aux coupon 
order may differ.
+        assert_eq!(hll4_bytes[..dense_end], expected_hll4_bytes[..dense_end]);
+        assert_eq!(hll4_bytes.len(), expected_hll4_bytes.len());
+
+        for target_type in [HllType::Hll4, HllType::Hll6, HllType::Hll8] {
+            assert_union_matches_sketch(union, target_type, target_type != 
HllType::Hll4);
         }
     }
 }
diff --git a/tests-integration/tests/serde_tests/theta.rs 
b/tests-integration/tests/serde_tests/theta.rs
index b22301e..4073d0f 100644
--- a/tests-integration/tests/serde_tests/theta.rs
+++ b/tests-integration/tests/serde_tests/theta.rs
@@ -415,3 +415,98 @@ fn union_serialization_matches_compact_result() {
         }
     }
 }
+
+#[test]
+fn union_compressed_serialization_matches_compact_result() {
+    for (lg_k, rows, probability, mixed_precision) in [
+        (5, 0, 1.0, false),
+        (5, 1, 1.0, false),
+        (5, 12, 1.0, false),
+        (5, 40, 1.0, false),
+        (5, 64, 0.5, false),
+        (5, 64, 1e-12, false),
+        (5, 64, 1.0, true),
+        (8, 5_000, 1.0, false),
+    ] {
+        let seed = 123;
+        let mut input = ThetaSketchBuilder::default()
+            .lg_k(8)
+            .seed(seed)
+            .sampling_probability(probability)
+            .build()
+            .unwrap();
+        for value in 0..rows {
+            input.update(value);
+        }
+        let mut union = ThetaUnionBuilder::default()
+            .lg_k(lg_k)
+            .seed(seed)
+            .build()
+            .unwrap();
+
+        let empty_compressed = union.serialize_compressed();
+        assert_eq!(
+            empty_compressed,
+            union.to_sketch(true).serialize_compressed()
+        );
+        assert_eq!(empty_compressed, union.serialize(true));
+        assert_eq!(empty_compressed[1], 3);
+
+        union.update(&input).unwrap();
+        if mixed_precision {
+            let mut other = ThetaSketchBuilder::default()
+                .lg_k(5)
+                .seed(seed)
+                .build()
+                .unwrap();
+            for value in 32..96 {
+                other.update(value);
+            }
+            union.update(&other.compact(true)).unwrap();
+        }
+
+        let compressed = union.serialize_compressed();
+        let expected_sketch = union.to_sketch(true);
+        assert_eq!(
+            compressed,
+            expected_sketch.serialize_compressed(),
+            "lg_k={lg_k}, rows={rows}, probability={probability}, 
mixed={mixed_precision}",
+        );
+
+        let num_retained = expected_sketch.num_retained();
+        if num_retained == 0 || (num_retained == 1 && 
!expected_sketch.is_estimation_mode()) {
+            assert_eq!(compressed[1], 3);
+            assert_eq!(compressed, union.serialize(true));
+        } else {
+            assert_eq!(compressed[1], 4);
+            assert!(compressed.len() <= union.serialize(true).len());
+        }
+
+        let restored = CompactThetaSketch::deserialize_with_seed(&compressed, 
seed).unwrap();
+        assert_eq!(restored.is_empty(), expected_sketch.is_empty());
+        assert_eq!(
+            restored.is_estimation_mode(),
+            expected_sketch.is_estimation_mode()
+        );
+        assert_eq!(restored.is_ordered(), expected_sketch.is_ordered());
+        assert_eq!(restored.theta(), expected_sketch.theta());
+        assert_eq!(restored.estimate(), expected_sketch.estimate());
+        assert_eq!(
+            restored
+                .iter()
+                .map(|entry| entry.hash())
+                .collect::<Vec<_>>(),
+            expected_sketch
+                .iter()
+                .map(|entry| entry.hash())
+                .collect::<Vec<_>>(),
+        );
+        assert_eq!(restored.serialize_compressed(), compressed);
+
+        union.reset();
+        assert_eq!(
+            union.serialize_compressed(),
+            union.to_sketch(true).serialize_compressed()
+        );
+    }
+}


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

Reply via email to