Struct HyperLogLogPlus 

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

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<u32, _> =
    HyperLogLogPlus::new(16, RandomState::new()).unwrap();

hllp.insert(&12345);
hllp.insert(&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.

Implementations

impl<H, B> HyperLogLogPlus<H, B>

where H: Hash + ?Sized, B: BuildHasher,

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

Creates a new HyperLogLogPlus instance.

pub fn merge<S, T>( &mut self, other: &HyperLogLogPlus<S, T>, ) -> Result<(), HyperLogLogError>

where S: Hash + ?Sized, 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.

pub fn insert_any<R>(&mut self, value: &R)

where R: Hash + ?Sized,

Inserts a new value, of any type, to the multiset.

Trait Implementations

impl<H, B> Clone for HyperLogLogPlus<H, B>

where H: Hash + ?Sized + Clone, B: BuildHasher + Clone,

fn clone(&self) -> HyperLogLogPlus<H, B>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<H, B> Debug for HyperLogLogPlus<H, B>

where H: Hash + ?Sized + Debug, B: BuildHasher + Debug,

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

Formats the value using the given formatter.

impl<'de, H, B> Deserialize<'de> for HyperLogLogPlus<H, B>

where H: Hash + ?Sized, B: BuildHasher + 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, B> HyperLogLog<H> for HyperLogLogPlus<H, B>

where H: Hash + ?Sized, B: BuildHasher,

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

👎Deprecated since 0.3.0: use insert() function instead.

Adds a new value to the multiset.

fn insert<Q>(&mut self, value: &Q)

where H: Borrow<Q>, Q: Hash + ?Sized,

Inserts a new value to the multiset.

fn count(&mut self) -> f64

Estimates the cardinality of the multiset.

impl<H, B> Serialize for HyperLogLogPlus<H, B>

where H: Hash + ?Sized, B: BuildHasher + Serialize,

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

where __S: Serializer,

Serialize this value into the given Serde serializer.