1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
use crate::algebraic_ops::alg_add_f64;
// Computes 2^-n by directly subtracting from the IEEE754 double exponent.
fn inv_pow2(n: u8) -> f64 {
let base = f64::to_bits(1.0);
f64::from_bits(base - ((n as u64) << 52))
}
/// HyperLogLog in Practice: Algorithmic Engineering of
/// a State of The Art Cardinality Estimation Algorithm
/// Stefan Heule, Marc Nunkesser, Alexander Hall
///
/// We use m = 256 which gives a relative error of ~6.5% of the cardinality
/// estimate. We don't bother with stuffing the counts in 6 bits, byte access is
/// fast.
///
/// The bias correction described in the paper is not implemented, so this is
/// somewhere in between HyperLogLog and HyperLogLog++.
#[derive(Clone)]
pub struct CardinalitySketch {
buckets: Box<[u8; 256]>,
}
impl Default for CardinalitySketch {
fn default() -> Self {
Self::new()
}
}
impl CardinalitySketch {
pub fn new() -> Self {
Self {
// This compiles to alloc_zeroed directly.
buckets: vec![0u8; 256].into_boxed_slice().try_into().unwrap(),
}
}
/// Add a new hash to the sketch.
pub fn insert(&mut self, mut h: u64) {
const ARBITRARY_ODD: u64 = 0x902813a5785dc787;
// We multiply by this arbitrarily chosen odd number and then take the
// top bits to ensure the sketch is influenced by all bits of the hash.
h = h.wrapping_mul(ARBITRARY_ODD);
let idx = (h >> 56) as usize;
let p = 1 + (h << 8).leading_zeros() as u8;
self.buckets[idx] = self.buckets[idx].max(p);
}
pub fn combine(&mut self, other: &CardinalitySketch) {
*self.buckets = std::array::from_fn(|i| std::cmp::max(self.buckets[i], other.buckets[i]));
}
pub fn estimate(&self) -> usize {
let m = 256.0;
let alpha_m = 0.7123 / (1.0 + 1.079 / m);
let mut sum = 0.0;
let mut num_zero = 0;
for x in self.buckets.iter() {
sum = alg_add_f64(sum, inv_pow2(*x));
num_zero += (*x == 0) as usize;
}
let est = (alpha_m * m * m) / sum;
let corr_est = if est <= 5.0 / 2.0 * m && num_zero != 0 {
// Small cardinality estimate, full 64-bit logarithm is overkill.
m * (m as f32 / num_zero as f32).ln() as f64
} else {
est
};
corr_est as usize
}
}