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 9cf7ddd feat(hll): expose composite cardinality estimates (#294)
9cf7ddd is described below
commit 9cf7ddd1d25f4435212a5c484f892eccb0360716
Author: edouardmulliez <[email protected]>
AuthorDate: Thu Oct 8 19:05:26 2026 +0200
feat(hll): expose composite cardinality estimates (#294)
Co-authored-by: tison <[email protected]>
---
CHANGELOG.md | 1 +
datasketches/src/hll/array4.rs | 5 ++
datasketches/src/hll/array6.rs | 5 ++
datasketches/src/hll/array8.rs | 5 ++
datasketches/src/hll/estimator.rs | 2 +-
datasketches/src/hll/sketch.rs | 28 ++++++
datasketches/src/hll/union.rs | 20 +++++
tests-integration/tests/hll_test/estimate.rs | 130 +++++++++++++++++++++++++++
tests-integration/tests/hll_test/main.rs | 1 +
9 files changed, 196 insertions(+), 1 deletion(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 4f366e1..5cfc3df 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -12,6 +12,7 @@ All significant changes to this project will be documented in
this file.
### New features
+* Add `HllSketch::composite_estimate` and `HllUnion::composite_estimate` to
query cardinality without relying on HIP update history, matching Java's
`getCompositeEstimate()`.
* `KllSketch` is now available behind the `kll` feature, with rank, quantile,
PMF, and CDF queries, merging, serialization, custom ordered item types, and a
`KllFloat` adapter for non-NaN floating-point values.
* Add `TDigestMut::quantiles` and `TDigest::quantiles` for querying several
ranks in one centroid scan while preserving input order.
* Add `FromIterator<TDigestMut>` as an alternative to incremental
`TDigestMut::merge` calls for combining owned partial sketches in a single
compression pass.
diff --git a/datasketches/src/hll/array4.rs b/datasketches/src/hll/array4.rs
index 1a13059..19c9632 100644
--- a/datasketches/src/hll/array4.rs
+++ b/datasketches/src/hll/array4.rs
@@ -241,6 +241,11 @@ impl Array4 {
.estimate(self.lg_config_k, self.cur_min, self.num_at_cur_min)
}
+ pub fn composite_estimate(&self) -> f64 {
+ self.estimator
+ .composite_estimate(self.lg_config_k, self.cur_min,
self.num_at_cur_min)
+ }
+
pub fn upper_bound(&self, num_std_dev: NumStdDev) -> f64 {
self.estimator.upper_bound(
self.lg_config_k,
diff --git a/datasketches/src/hll/array6.rs b/datasketches/src/hll/array6.rs
index a1b0032..c29a901 100644
--- a/datasketches/src/hll/array6.rs
+++ b/datasketches/src/hll/array6.rs
@@ -123,6 +123,11 @@ impl Array6 {
self.estimator.estimate(self.lg_config_k, 0, self.num_zeros)
}
+ pub fn composite_estimate(&self) -> f64 {
+ self.estimator
+ .composite_estimate(self.lg_config_k, 0, self.num_zeros)
+ }
+
pub fn upper_bound(&self, num_std_dev: NumStdDev) -> f64 {
self.estimator
.upper_bound(self.lg_config_k, 0, self.num_zeros, num_std_dev)
diff --git a/datasketches/src/hll/array8.rs b/datasketches/src/hll/array8.rs
index a2f60aa..355bcc1 100644
--- a/datasketches/src/hll/array8.rs
+++ b/datasketches/src/hll/array8.rs
@@ -87,6 +87,11 @@ impl Array8 {
self.estimator.estimate(self.lg_config_k, 0, self.num_zeros)
}
+ pub fn composite_estimate(&self) -> f64 {
+ self.estimator
+ .composite_estimate(self.lg_config_k, 0, self.num_zeros)
+ }
+
pub fn upper_bound(&self, num_std_dev: NumStdDev) -> f64 {
self.estimator
.upper_bound(self.lg_config_k, 0, self.num_zeros, num_std_dev)
diff --git a/datasketches/src/hll/estimator.rs
b/datasketches/src/hll/estimator.rs
index 1a22809..457dff8 100644
--- a/datasketches/src/hll/estimator.rs
+++ b/datasketches/src/hll/estimator.rs
@@ -182,7 +182,7 @@ impl Estimator {
}
/// Selects between bias-corrected HLL and bitmap estimates using their
empirical crossover.
- fn composite_estimate(&self, lg_config_k: u8, cur_min: u8, num_at_cur_min:
u32) -> f64 {
+ pub fn composite_estimate(&self, lg_config_k: u8, cur_min: u8,
num_at_cur_min: u32) -> f64 {
let raw_estimate = self.raw_estimate(lg_config_k);
let x_arr = composite_interpolation::get_x_arr(lg_config_k);
diff --git a/datasketches/src/hll/sketch.rs b/datasketches/src/hll/sketch.rs
index 437062f..06dd823 100644
--- a/datasketches/src/hll/sketch.rs
+++ b/datasketches/src/hll/sketch.rs
@@ -232,6 +232,34 @@ impl HllSketch {
}
}
+ /// Returns the current cardinality estimate that never depends on
+ /// the order in which values were inserted.
+ ///
+ /// This can be less accurate than [`estimate`](Self::estimate).
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::hll::HllSketch;
+ /// use datasketches::hll::HllType;
+ ///
+ /// let mut sketch = HllSketch::new(12, HllType::Hll4).unwrap();
+ /// for value in 0..10_000 {
+ /// sketch.update(value);
+ /// }
+ /// let estimate = sketch.composite_estimate();
+ /// assert!((estimate - 10_000.0).abs() < 500.0);
+ /// ```
+ pub fn composite_estimate(&self) -> f64 {
+ match &self.mode {
+ Mode::List { list, .. } => list.container().estimate(),
+ Mode::Set { set, .. } => set.container().estimate(),
+ Mode::Array4(arr) => arr.composite_estimate(),
+ Mode::Array6(arr) => arr.composite_estimate(),
+ Mode::Array8(arr) => arr.composite_estimate(),
+ }
+ }
+
/// Returns the upper confidence bound for `num_std_dev` standard
deviations.
///
/// # Examples
diff --git a/datasketches/src/hll/union.rs b/datasketches/src/hll/union.rs
index f16cebc..0f6e20e 100644
--- a/datasketches/src/hll/union.rs
+++ b/datasketches/src/hll/union.rs
@@ -307,6 +307,26 @@ impl HllUnion {
self.gadget.estimate()
}
+ /// Returns the union's cardinality estimate using the composite estimator.
+ ///
+ /// See [`HllSketch::composite_estimate`].
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::hll::HllUnion;
+ ///
+ /// let mut union = HllUnion::new(12).unwrap();
+ /// for value in 0..10_000 {
+ /// union.update_value(value);
+ /// }
+ /// let estimate = union.composite_estimate();
+ /// assert!((estimate - 10_000.0).abs() < 500.0);
+ /// ```
+ pub fn composite_estimate(&self) -> f64 {
+ self.gadget.composite_estimate()
+ }
+
/// Returns the upper confidence bound for `num_std_dev` standard
deviations.
///
/// # Examples
diff --git a/tests-integration/tests/hll_test/estimate.rs
b/tests-integration/tests/hll_test/estimate.rs
new file mode 100644
index 0000000..3724259
--- /dev/null
+++ b/tests-integration/tests/hll_test/estimate.rs
@@ -0,0 +1,130 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use datasketches::hll::HllSketch;
+use datasketches::hll::HllType;
+use datasketches::hll::HllUnion;
+use googletest::assert_that;
+use googletest::prelude::near;
+
+const HLL_TYPES: [HllType; 3] = [HllType::Hll4, HllType::Hll6, HllType::Hll8];
+
+fn make_sketch(hll_type: HllType, values: impl Iterator<Item = u64>) ->
HllSketch {
+ let mut sketch = HllSketch::new(11, hll_type).unwrap();
+ for value in values {
+ sketch.update(value);
+ }
+ sketch
+}
+
+#[test]
+fn composite_estimate_matches_coupon_estimate_in_list_and_set_modes() {
+ for hll_type in HLL_TYPES {
+ for n in [0, 3, 100] {
+ let sketch = make_sketch(hll_type, 0..n);
+ assert_eq!(sketch.composite_estimate(), sketch.estimate());
+ }
+ }
+}
+
+#[test]
+fn composite_estimate_is_independent_of_insertion_order() {
+ for hll_type in HLL_TYPES {
+ for n in [1_000, 10_000, 100_000] {
+ let forward = make_sketch(hll_type, 0..n);
+ let reverse = make_sketch(hll_type, (0..n).rev());
+ assert_ne!(forward.estimate(), reverse.estimate());
+ assert_that!(
+ forward.composite_estimate(),
+ near(reverse.composite_estimate(), 1e-9),
+ "type={hll_type:?}, n={n}"
+ );
+ }
+ }
+}
+
+#[test]
+fn composite_estimate_matches_estimate_after_register_merge() {
+ for hll_type in HLL_TYPES {
+ for n in [1_000, 10_000, 100_000] {
+ let sketch = make_sketch(hll_type, 0..n);
+ let mut union = HllUnion::new(sketch.lg_config_k()).unwrap();
+ union.update(&sketch);
+ union.update(&sketch);
+ assert_that!(sketch.composite_estimate(), near(union.estimate(),
1e-9));
+ assert_eq!(union.composite_estimate(), union.estimate());
+ for result_type in HLL_TYPES {
+ assert_that!(
+ union.to_sketch(result_type).composite_estimate(),
+ near(union.estimate(), 1e-9)
+ );
+ }
+ }
+ }
+}
+
+#[test]
+fn composite_estimate_preserves_hip_state_and_subsequent_updates() {
+ for hll_type in HLL_TYPES {
+ let mut sketch = make_sketch(hll_type, 0..10_000);
+ let mut control = sketch.clone();
+ let estimate = sketch.estimate();
+ let bytes = sketch.serialize();
+ assert_ne!(sketch.composite_estimate(), estimate);
+ assert_eq!(sketch.estimate(), estimate);
+ assert_eq!(sketch.serialize(), bytes);
+
+ let decoded = HllSketch::deserialize(&bytes).unwrap();
+ assert_eq!(decoded.composite_estimate(), sketch.composite_estimate());
+ assert_eq!(decoded.estimate(), estimate);
+
+ for value in 10_000..20_000_u64 {
+ sketch.update(value);
+ control.update(value);
+ }
+ assert_eq!(sketch.serialize(), control.serialize());
+ }
+}
+
+#[test]
+fn union_composite_estimate_works_with_direct_updates_and_single_sketch() {
+ for n in [0, 3, 100, 10_000] {
+ let sketch = make_sketch(HllType::Hll8, 0..n);
+ let mut direct = HllUnion::new(11).unwrap();
+ for value in 0..n {
+ direct.update_value(value);
+ }
+ let direct_estimate = direct.estimate();
+ assert_eq!(direct.composite_estimate(), sketch.composite_estimate());
+ assert_eq!(direct.estimate(), direct_estimate);
+
+ for hll_type in HLL_TYPES {
+ let sketch = make_sketch(hll_type, 0..n);
+ let mut union = HllUnion::new(11).unwrap();
+ union.update(&sketch);
+ let hip_estimate = union.estimate();
+ assert_eq!(hip_estimate, sketch.estimate());
+ assert_that!(
+ union.composite_estimate(),
+ near(sketch.composite_estimate(), 1e-9)
+ );
+ assert_eq!(union.estimate(), hip_estimate);
+ union.reset();
+ assert_eq!(union.composite_estimate(), 0.0);
+ }
+ }
+}
diff --git a/tests-integration/tests/hll_test/main.rs
b/tests-integration/tests/hll_test/main.rs
index 30fb7dc..5a892ff 100644
--- a/tests-integration/tests/hll_test/main.rs
+++ b/tests-integration/tests/hll_test/main.rs
@@ -16,5 +16,6 @@
// under the License.
mod bounds;
+mod estimate;
mod union;
mod update;
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
