subms_hyperloglog/features/
union_intersect.rs

1//! Set operations on HyperLogLog sketches.
2//!
3//! - `estimate_union(a, b)` is exact in the HLL sense: merge the two
4//!   sketches register-wise and estimate. Same operation as the base
5//!   `merge()` method, just non-destructive.
6//! - `estimate_intersect(a, b)` uses inclusion-exclusion:
7//!   `|A and B| ~= |A| + |B| - |A or B|`. This is the only practical HLL
8//!   intersection. Be aware: when A and B mostly overlap, the variance
9//!   of the subtraction is large relative to the result, so the
10//!   estimator gets noisy. The error bound is `~1.04/sqrt(m) * (|A| +
11//!   |B|)`, not `~1.04/sqrt(m) * |A and B|`. For nearly-disjoint or
12//!   nearly-identical sets, prefer Apache DataSketches' Theta sketches.
13
14use crate::{HllError, HyperLogLog};
15
16/// Distinct count of the union, exact in the HLL sense.
17pub fn estimate_union(a: &HyperLogLog, b: &HyperLogLog) -> Result<f64, HllError> {
18    if a.precision() != b.precision() {
19        return Err(HllError::PrecisionMismatch {
20            left: a.precision(),
21            right: b.precision(),
22        });
23    }
24    let mut merged = HyperLogLog::new(a.precision());
25    let ra = a.registers();
26    let rb = b.registers();
27    // Reach into the merged buffer; the base `merge()` would work
28    // too, but doing one pass keeps the cost obvious.
29    merged.apply_paired_max(ra, rb);
30    Ok(merged.estimate())
31}
32
33/// Distinct count of the intersection via inclusion-exclusion. Clamps to
34/// `>= 0` since a negative estimate is a hard signal of large relative error.
35pub fn estimate_intersect(a: &HyperLogLog, b: &HyperLogLog) -> Result<f64, HllError> {
36    let ea = a.estimate();
37    let eb = b.estimate();
38    let union = estimate_union(a, b)?;
39    let inter = ea + eb - union;
40    Ok(inter.max(0.0))
41}
42
43/// Absolute error the inclusion-exclusion estimate carries at one standard
44/// deviation. It scales with `|A| + |B|`, so a thin overlap between two large
45/// sets can come back with an error bar wider than the answer. Check it
46/// against the estimate before believing an intersection.
47pub fn intersect_error_bound(a: &HyperLogLog, b: &HyperLogLog) -> Result<f64, HllError> {
48    if a.precision() != b.precision() {
49        return Err(HllError::PrecisionMismatch {
50            left: a.precision(),
51            right: b.precision(),
52        });
53    }
54    Ok(a.standard_error() * (a.estimate() + b.estimate()))
55}
56
57// Tiny extension on the base so we don't expose register internals
58// to every caller. Lives here next to the only consumer.
59impl HyperLogLog {
60    pub(crate) fn apply_paired_max(&mut self, a: &[u8], b: &[u8]) {
61        debug_assert_eq!(a.len(), self.registers().len());
62        debug_assert_eq!(b.len(), self.registers().len());
63        for (i, (x, y)) in a.iter().zip(b.iter()).enumerate() {
64            let m = (*x).max(*y);
65            if m > self.registers[i] {
66                self.registers[i] = m;
67            }
68        }
69    }
70}
71
72#[cfg(test)]
73#[path = "union_intersect_tests.rs"]
74mod tests;
subms_hyperloglog/features/union_intersect.rs

subms_hyperloglog/features/
union_intersect.rs
