oxedyne/fe2o3/fe2o3_data/src/hll/mod.rs
2.0 KiB, 5 runs
created by r1870400018:11202, which is this file's identity for as long as the history lasts, whatever it is later renamed to
download · who wrote it · its history
| 1 | //! A HyperLogLog cardinality-sketch primitive for the Hematite distributed |
| 2 | //! Ozone layer. |
| 3 | //! |
| 4 | //! The sketch estimates the number of distinct 64-bit hashes it has observed, |
| 5 | //! in fixed space regardless of the true cardinality. Two sketches of equal |
| 6 | //! precision merge by register-wise maximum into a sketch that represents |
| 7 | //! the union of their inputs -- without revealing which input supplied which |
| 8 | //! element. |
| 9 | //! |
| 10 | //! # Hash function is the caller's choice |
| 11 | //! |
| 12 | //! This crate does not bundle a hash function. [`sketch::HyperLogLog::add_hash`] |
| 13 | //! takes a `u64` directly. Callers pick a hash appropriate to their domain: |
| 14 | //! SeaHash for generic uniformly-distributed bytes, SipHash for keyed |
| 15 | //! resistance to adversarial inputs, or a truncated cryptographic hash when |
| 16 | //! the sketch is part of a larger authenticated protocol. The sketch itself |
| 17 | //! makes no guarantee about adversarial resistance -- if your inputs come |
| 18 | //! from a potentially hostile source, use a keyed hash. |
| 19 | //! |
| 20 | //! # Distributed Ozone usage |
| 21 | //! |
| 22 | //! See #raw("sec_ozone.typ") §"Network Size Estimation: HyperLogLog". Every |
| 23 | //! peer keeps a 16 KiB sketch (precision `p = 14`) tracking the peer ids it |
| 24 | //! has observed. Every few hours peers swap sketches with a small sample of |
| 25 | //! the network, merge, and update their local estimate of $N$. The merged |
| 26 | //! result converges to within ~2% of the true cardinality within 5-10 rounds. |
| 27 | //! |
| 28 | //! # Example |
| 29 | //! |
| 30 | //! ``` |
| 31 | //! use oxedyne_fe2o3_core::prelude::*; |
| 32 | //! use oxedyne_fe2o3_data::hll::{HyperLogLog, P_DEFAULT}; |
| 33 | //! |
| 34 | //! # fn main() -> Outcome<()> { |
| 35 | //! let mut sketch = res!(HyperLogLog::new(P_DEFAULT)); |
| 36 | //! for i in 0u64..1_000 { |
| 37 | //! // Caller-chosen hash: here we use a trivial mixer for demonstration. |
| 38 | //! let h = i.wrapping_mul(0x9e37_79b9_7f4a_7c15); |
| 39 | //! sketch.add_hash(h); |
| 40 | //! } |
| 41 | //! let estimate = sketch.estimate_rounded(); |
| 42 | //! assert!(estimate > 900 && estimate < 1100, "estimate = {}", estimate); |
| 43 | //! # Ok(()) |
| 44 | //! # } |
| 45 | //! ``` |
| 46 | mod sketch; |
| 47 | |
| 48 | pub use sketch::{ |
| 49 | HyperLogLog, |
| 50 | P_DEFAULT, |
| 51 | P_MAX, |
| 52 | P_MIN, |
| 53 | }; |