Struct hyperloglogplus::HyperLogLogPlus

pub struct HyperLogLogPlus<H: ?Sized, B> where
    H: Hash,
    B: BuildHasher,  { /* fields omitted */ }

Implements the HyperLogLog++ algorithm for cardinality estimation.

This implementation is based on the paper:

HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm.

• Uses 6-bit registers, packed in a 32-bit unsigned integer. Thus, every five registers 2 bits are not used.
• In small cardinalities, a sparse representation is used which allows for higher precision in estimations.
• Performs bias correction using the empirical data provided by Google (can be found here).
• Supports serialization/deserialization through serde.

Examples

use std::collections::hash_map::RandomState;
use hyperloglogplus::{HyperLogLog, HyperLogLogPlus};

let mut hllp: HyperLogLogPlus<u64, RandomState> =
    HyperLogLogPlus::new(16, RandomState::new()).unwrap();

hllp.add(&12345);
hllp.add(&23456);

assert_eq!(hllp.count().trunc() as u32, 2);

References

• "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm", Philippe Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier.
• "HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm", Stefan Heule, Marc Nunkesser and Alexander Hall.
• "Appendix to HyperLogLog in Practice: Algorithmic Engineering of a State of the Art Cardinality Estimation Algorithm", Stefan Heule, Marc Nunkesser and Alexander Hall.

Methods

impl<H: ?Sized, B> HyperLogLogPlus<H, B> where
    H: Hash,
    B: BuildHasher, 

pub fn new(precision: u8, builder: B) -> Result<Self, HyperLogLogError>

Creates a new HyperLogLogPlus instance.

pub fn merge<S: ?Sized, T>(
    &mut self,
    other: &HyperLogLogPlus<S, T>
) -> Result<(), HyperLogLogError> where
    S: Hash,
    T: BuildHasher, 

Merges the other HyperLogLogPlus instance into self.

Both sketches must have the same precision. Merge can trigger the transition from sparse to normal representation.

Trait Implementations

impl<H: Debug + ?Sized, B: Debug> Debug for HyperLogLogPlus<H, B> where
    H: Hash,
    B: BuildHasher, 

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<'de, H: ?Sized, B> Deserialize<'de> for HyperLogLogPlus<H, B> where
    H: Hash,
    B: BuildHasher,
    B: Deserialize<'de>, 

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
    __D: Deserializer<'de>, 

Deserialize this value from the given Serde deserializer.

impl<H: ?Sized, B> HyperLogLog<H> for HyperLogLogPlus<H, B> where
    H: Hash,
    B: BuildHasher, 

fn add(&mut self, value: &H)

Adds a new value to the multiset.

fn count(&mut self) -> f64

Estimates the cardinality of the multiset.

impl<H: ?Sized, B> Serialize for HyperLogLogPlus<H, B> where
    H: Hash,
    B: BuildHasher,
    B: Serialize, 

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error> where
    __S: Serializer, 

Serialize this value into the given Serde serializer.