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 dd81c80 fix(hll): clamp the HLL-mode lower bound to the non-zero
register count (#237)
dd81c80 is described below
commit dd81c8041bd8ef991a6f83aa010a895715b90e7b
Author: Jaideep Pyne <[email protected]>
AuthorDate: Fri Aug 28 15:55:27 2026 +0530
fix(hll): clamp the HLL-mode lower bound to the non-zero register count
(#237)
Co-authored-by: Claude Opus 4.8 <[email protected]>
Co-authored-by: tison <[email protected]>
---
CHANGELOG.md | 1 +
datasketches/src/hll/estimator.rs | 39 +++-
.../tests/hll_test/{update.rs => bounds.rs} | 204 ++++-----------------
tests-integration/tests/hll_test/main.rs | 1 +
tests-integration/tests/hll_test/update.rs | 107 -----------
5 files changed, 77 insertions(+), 275 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 69f89af..989f148 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -27,6 +27,7 @@ All significant changes to this project will be documented in
this file.
* T-Digest compression now supports `k = u16::MAX` without overflowing.
* T-Digest rejects truncated serialized payloads before allocating, and
updating a deserialized digest no longer allows its buffered state to grow
without bound.
* Compact HLL4 images now restore all register values correctly.
+* `HllSketch::lower_bound` now uses the number of non-zero registers as a
floor in HLL mode, matching Java, C++, and Go and avoiding a bound below the
distinct count already proven by register hits.
* HLL, Theta, and Tuple deserializers now return `InvalidData` for malformed
payload sizes and entry counts instead of risking oversized allocations or
decoding failures.
* Malformed CPC images now return `InvalidData` instead of panicking.
* Seeded deserializers now return `InvalidData` rather than panicking when the
caller supplies a seed whose hash is the reserved zero value.
diff --git a/datasketches/src/hll/estimator.rs
b/datasketches/src/hll/estimator.rs
index e81a859..903e780 100644
--- a/datasketches/src/hll/estimator.rs
+++ b/datasketches/src/hll/estimator.rs
@@ -148,6 +148,9 @@ impl HipEstimator {
///
/// Returns the lower confidence bound for the cardinality estimate.
///
+ /// Each non-zero register requires a distinct item, so their count is a
hard floor
+ /// for the lower bound. If `cur_min` is non-zero, all `k` registers are
non-zero.
+ ///
/// # Arguments
///
/// * `lg_config_k`: Log2 of number of registers (k)
@@ -163,8 +166,14 @@ impl HipEstimator {
) -> f64 {
let estimate = self.estimate(lg_config_k, cur_min, num_at_cur_min);
let rse = get_rel_err(lg_config_k, false, self.out_of_order,
num_std_dev);
+ let config_k = 1u32 << lg_config_k;
+ let num_nonzero_registers = if cur_min == 0 {
+ config_k - num_at_cur_min
+ } else {
+ config_k
+ };
// RSE is positive for lower bounds, so (1 + rse) > 1, making bound <
estimate
- estimate / (1.0 + rse)
+ (estimate / (1.0 + rse)).max(f64::from(num_nonzero_registers))
}
/// Get raw HLL estimate using standard HyperLogLog formula
@@ -498,6 +507,34 @@ mod tests {
use super::*;
+ #[test]
+ fn lower_bound_is_clamped_to_the_non_zero_register_count() {
+ let lg_config_k = 4;
+ let mut estimator = HipEstimator::new(lg_config_k);
+ for _ in 0..8 {
+ estimator.update(lg_config_k, 0, 1);
+ }
+
+ assert_eq!(
+ estimator.lower_bound(lg_config_k, 0, 8, NumStdDev::Three),
+ 8.0
+ );
+ }
+
+ #[test]
+ fn lower_bound_is_clamped_to_config_k_when_every_register_is_hit() {
+ let lg_config_k = 4;
+ let mut estimator = HipEstimator::new(lg_config_k);
+ for _ in 0..16 {
+ estimator.update(lg_config_k, 0, 1);
+ }
+
+ assert_eq!(
+ estimator.lower_bound(lg_config_k, 1, 16, NumStdDev::Three),
+ 16.0
+ );
+ }
+
#[test]
fn test_estimator_initialization() {
let est = HipEstimator::new(10); // 1024 registers
diff --git a/tests-integration/tests/hll_test/update.rs
b/tests-integration/tests/hll_test/bounds.rs
similarity index 52%
copy from tests-integration/tests/hll_test/update.rs
copy to tests-integration/tests/hll_test/bounds.rs
index 4aecd0b..159c01f 100644
--- a/tests-integration/tests/hll_test/update.rs
+++ b/tests-integration/tests/hll_test/bounds.rs
@@ -16,9 +16,9 @@
// under the License.
use datasketches::common::NumStdDev;
-use datasketches::error::ErrorKind;
use datasketches::hll::HllSketch;
use datasketches::hll::HllType;
+use datasketches::hll::HllUnion;
use googletest::assert_that;
use googletest::prelude::all;
use googletest::prelude::ge;
@@ -27,182 +27,52 @@ use googletest::prelude::le;
use googletest::prelude::lt;
use googletest::prelude::near;
-#[test]
-fn test_basic_update() {
- let mut sketch = HllSketch::new(12, HllType::Hll8).unwrap();
-
- // Initially empty
- assert_eq!(sketch.estimate(), 0.0);
-
- // Update with some values
- for i in 0..100 {
- sketch.update(i);
- }
-
- let estimate = sketch.estimate();
- assert_that!(estimate, gt(0.0));
- assert_that!(estimate, near(100.0, 20.0));
-}
-
-#[test]
-fn test_list_to_set_promotion() {
- // Use lg_k=12, which has promotion threshold ~512 for List→Set
- let mut sketch = HllSketch::new(12, HllType::Hll8).unwrap();
-
- // Add enough unique values to trigger promotion
- for i in 0..600 {
- sketch.update(i);
- }
-
- let estimate = sketch.estimate();
- assert_that!(estimate, near(600.0, 100.0));
-}
-
-#[test]
-fn test_set_to_hll_promotion() {
- // Use lg_k=10 (K=1024), set promotes at 75% = 768
- let mut sketch = HllSketch::new(10, HllType::Hll8).unwrap();
-
- // Add enough values to trigger List→Set→HLL promotions
- for i in 0..1000 {
- sketch.update(i);
+fn hll_mode_sketch(lg_k: u8, hll_type: HllType, n: u64) -> HllSketch {
+ let mut sketch = HllSketch::new(lg_k, hll_type).unwrap();
+ for value in 0..n {
+ sketch.update(value);
}
-
- let estimate = sketch.estimate();
- assert_that!(estimate, near(1000.0, 150.0));
+ sketch
}
-#[test]
-fn test_duplicate_handling() {
- let mut sketch = HllSketch::new(12, HllType::Hll8).unwrap();
-
- // Add same values multiple times
- for _ in 0..10 {
- for i in 0..100 {
- sketch.update(i);
+fn hll_mode_union(lg_k: u8, hll_type: HllType, n: u64) -> HllSketch {
+ let mut even = HllSketch::new(lg_k, hll_type).unwrap();
+ let mut odd = HllSketch::new(lg_k, hll_type).unwrap();
+ for value in 0..n {
+ if value % 2 == 0 {
+ even.update(value);
+ } else {
+ odd.update(value);
}
}
-
- // Estimate should reflect ~100 unique values, not 1000
- let estimate = sketch.estimate();
- assert_that!(estimate, near(100.0, 20.0));
-}
-
-#[test]
-fn test_different_types() {
- let mut sketch = HllSketch::new(10, HllType::Hll8).unwrap();
-
- // Mix different types
- sketch.update(42i32);
- sketch.update("hello");
- sketch.update(100u64);
- sketch.update(true);
- sketch.update(vec![1, 2, 3]);
-
- let estimate = sketch.estimate();
- assert_that!(estimate, ge(5.0));
-}
-
-#[test]
-fn test_hll4_type() {
- let mut sketch = HllSketch::new(12, HllType::Hll4).unwrap();
-
- for i in 0..1000 {
- sketch.update(i);
- }
-
- let estimate = sketch.estimate();
- assert_that!(estimate, near(1000.0, 200.0));
-}
-
-#[test]
-fn test_hll6_type() {
- let mut sketch = HllSketch::new(12, HllType::Hll6).unwrap();
-
- for i in 0..1000 {
- sketch.update(i);
+ let mut union = HllUnion::new(lg_k).unwrap();
+ union.update(&even);
+ union.update(&odd);
+ union.to_sketch(hll_type)
+}
+
+#[test]
+fn hll_mode_lower_bound_matches_cross_language_register_floor() {
+ // C++ reports a floor of 8 for this stream in all three target
representations.
+ for hll_type in [HllType::Hll4, HllType::Hll6, HllType::Hll8] {
+ let sketch = hll_mode_sketch(4, hll_type, 12);
+ assert_eq!(
+ sketch.lower_bound(NumStdDev::Three),
+ 8.0,
+ "type={hll_type:?}"
+ );
}
- let estimate = sketch.estimate();
- assert_that!(estimate, near(1000.0, 200.0));
-}
-
-#[test]
-fn test_serialization_roundtrip_after_updates() {
- let mut sketch1 = HllSketch::new(12, HllType::Hll8).unwrap();
-
- // Add values and promote through all modes
- for i in 0..2000 {
- sketch1.update(i);
- }
-
- let estimate1 = sketch1.estimate();
-
- // Serialize and deserialize
- let bytes = sketch1.serialize();
- let sketch2 = HllSketch::deserialize(&bytes).unwrap();
-
- let estimate2 = sketch2.estimate();
-
- // Estimates should match after round-trip (allow some numerical error)
- let relative_error = (estimate1 - estimate2).abs() / estimate1;
+ // The one-standard-deviation bound remains above the register floor.
+ let sketch = hll_mode_sketch(4, HllType::Hll8, 12);
assert_that!(
- relative_error,
- lt(0.05),
- "estimate1={estimate1}, estimate2={estimate2}"
+ sketch.lower_bound(NumStdDev::One),
+ near(9.946968965192236, 1e-9)
);
-}
-
-#[test]
-fn test_large_cardinality() {
- let mut sketch = HllSketch::new(14, HllType::Hll8).unwrap();
-
- // Add 100K unique values
- for i in 0..100_000 {
- sketch.update(i);
- }
-
- let estimate = sketch.estimate();
- let relative_error = (estimate - 100_000.0).abs() / 100_000.0;
-
- // For lg_k=14, relative error should be ~1.04%
- assert_that!(relative_error, lt(0.05));
-}
-
-#[test]
-fn test_equals_method() {
- let mut sketch1 = HllSketch::new(10, HllType::Hll8).unwrap();
- let mut sketch2 = HllSketch::new(10, HllType::Hll8).unwrap();
-
- // Both start equal (empty)
- assert!(sketch1.eq(&sketch2));
- // Add same values to both
- for i in 0..100 {
- sketch1.update(i);
- sketch2.update(i);
- }
-
- // Should still be equal
- assert!(sketch1.eq(&sketch2));
-
- // Add different value to sketch2
- sketch2.update(999);
-
- // Now they're different
- assert!(!sketch1.eq(&sketch2));
-}
-
-#[test]
-fn test_invalid_lg_k_low_returns_error() {
- let error = HllSketch::new(3, HllType::Hll8).unwrap_err();
- assert_eq!(error.kind(), ErrorKind::InvalidArgument);
-}
-
-#[test]
-fn test_invalid_lg_k_high_returns_error() {
- let error = HllSketch::new(22, HllType::Hll8).unwrap_err();
- assert_eq!(error.kind(), ErrorKind::InvalidArgument);
+ // The same floor applies when a union selects the out-of-order estimator.
+ let sketch = hll_mode_union(7, HllType::Hll4, 40);
+ assert_eq!(sketch.lower_bound(NumStdDev::Three), 34.0);
}
#[test]
diff --git a/tests-integration/tests/hll_test/main.rs
b/tests-integration/tests/hll_test/main.rs
index e56cecc..30fb7dc 100644
--- a/tests-integration/tests/hll_test/main.rs
+++ b/tests-integration/tests/hll_test/main.rs
@@ -15,5 +15,6 @@
// specific language governing permissions and limitations
// under the License.
+mod bounds;
mod union;
mod update;
diff --git a/tests-integration/tests/hll_test/update.rs
b/tests-integration/tests/hll_test/update.rs
index 4aecd0b..50fd0b4 100644
--- a/tests-integration/tests/hll_test/update.rs
+++ b/tests-integration/tests/hll_test/update.rs
@@ -15,15 +15,12 @@
// specific language governing permissions and limitations
// under the License.
-use datasketches::common::NumStdDev;
use datasketches::error::ErrorKind;
use datasketches::hll::HllSketch;
use datasketches::hll::HllType;
use googletest::assert_that;
-use googletest::prelude::all;
use googletest::prelude::ge;
use googletest::prelude::gt;
-use googletest::prelude::le;
use googletest::prelude::lt;
use googletest::prelude::near;
@@ -204,107 +201,3 @@ fn test_invalid_lg_k_high_returns_error() {
let error = HllSketch::new(22, HllType::Hll8).unwrap_err();
assert_eq!(error.kind(), ErrorKind::InvalidArgument);
}
-
-#[test]
-fn test_bounds_basic() {
- let mut sketch = HllSketch::new(12, HllType::Hll8).unwrap();
-
- // Add 1000 unique values
- for i in 0..1000 {
- sketch.update(i);
- }
-
- let estimate = sketch.estimate();
- let upper1 = sketch.upper_bound(NumStdDev::One);
- let lower1 = sketch.lower_bound(NumStdDev::One);
- let upper2 = sketch.upper_bound(NumStdDev::Two);
- let lower2 = sketch.lower_bound(NumStdDev::Two);
- let upper3 = sketch.upper_bound(NumStdDev::Three);
- let lower3 = sketch.lower_bound(NumStdDev::Three);
-
- // Basic sanity checks
- assert_that!(estimate, ge(lower1));
- assert_that!(estimate, le(upper1));
-
- // Bounds should widen with more standard deviations
- assert_that!(lower2, le(lower1));
- assert_that!(upper1, le(upper2));
- assert_that!(lower3, le(lower2));
- assert_that!(upper2, le(upper3));
-
- // Bounds should be reasonable (within 50% for 3-sigma)
- assert_that!(lower3, gt(estimate * 0.5));
- assert_that!(upper3, lt(estimate * 1.5));
-}
-
-#[test]
-fn test_bounds_all_modes() {
- // Test List mode (small cardinality)
- let mut sketch = HllSketch::new(12, HllType::Hll8).unwrap();
- for i in 0..10 {
- sketch.update(i);
- }
- let estimate = sketch.estimate();
- let upper = sketch.upper_bound(NumStdDev::Two);
- let lower = sketch.lower_bound(NumStdDev::Two);
- assert_that!(estimate, all!(ge(lower), le(upper)), "mode: LIST");
-
- // Test Set mode (medium cardinality)
- for i in 10..100 {
- sketch.update(i);
- }
- let estimate = sketch.estimate();
- let upper = sketch.upper_bound(NumStdDev::Two);
- let lower = sketch.lower_bound(NumStdDev::Two);
- assert_that!(estimate, all!(ge(lower), le(upper)), "mode: SET");
-
- // Test HLL mode (large cardinality)
- for i in 100..5000 {
- sketch.update(i);
- }
- let estimate = sketch.estimate();
- let upper = sketch.upper_bound(NumStdDev::Two);
- let lower = sketch.lower_bound(NumStdDev::Two);
- assert_that!(estimate, all!(ge(lower), le(upper)), "mode: HLL");
-}
-
-#[test]
-fn test_bounds_different_lg_k() {
- // Smaller lg_k should have wider bounds (higher RSE)
- let mut sketch_small = HllSketch::new(8, HllType::Hll8).unwrap(); //
lg_k=8, k=256
- let mut sketch_large = HllSketch::new(14, HllType::Hll8).unwrap(); //
lg_k=14, k=16384
-
- for i in 0..1000 {
- sketch_small.update(i);
- sketch_large.update(i);
- }
-
- let est_small = sketch_small.estimate();
- let est_large = sketch_large.estimate();
-
- let upper_small = sketch_small.upper_bound(NumStdDev::Two);
- let lower_small = sketch_small.lower_bound(NumStdDev::Two);
- let upper_large = sketch_large.upper_bound(NumStdDev::Two);
- let lower_large = sketch_large.lower_bound(NumStdDev::Two);
-
- // Calculate relative width of confidence intervals
- let width_small = (upper_small - lower_small) / est_small;
- let width_large = (upper_large - lower_large) / est_large;
-
- // Smaller sketch should have wider relative confidence interval
- assert_that!(width_small, gt(width_large));
-}
-
-#[test]
-fn test_bounds_empty_sketch() {
- let sketch = HllSketch::new(12, HllType::Hll8).unwrap();
-
- let estimate = sketch.estimate();
- let upper = sketch.upper_bound(NumStdDev::Two);
- let lower = sketch.lower_bound(NumStdDev::Two);
-
- assert_eq!(estimate, 0.0, "Empty sketch should have 0 estimate");
- assert_that!(lower, ge(0.0));
- assert_that!(upper, ge(0.0));
- assert_that!(lower, le(upper));
-}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
