Trait HyperLogLogTrait

pub trait HyperLogLogTrait<P: Precision + WordType<BITS>, const BITS: usize>: Sized {
    const INTERMEDIATE_RANGE_CORRECTION_THRESHOLD: f32 = _;
    const LINEAR_COUNT_THRESHOLD: f32 = _;
    const LOWER_REGISTER_MASK: u32 = _;
    const LOWER_PRECISION_MASK: usize = _;
    const NOT_LOWER_PRECISION_MASK: u64 = _;
    const NUMBER_OF_PADDING_BITS: usize = _;
    const PADDING_BITS_MASK: u32 = _;
    const NUMBER_OF_PADDING_REGISTERS: usize = _;
    const LAST_WORD_PADDING_BITS_MASK: u32 = _;
    const UPPER_PRECISION_MASK: usize = _;
    const NUMBER_OF_REGISTERS_IN_WORD: usize = _;

    // Required methods
    fn get_number_of_zero_registers(&self) -> usize;
    fn get_words(&self) -> &P::Words;

    // Provided methods
    fn adjust_estimate(raw_estimate: f32) -> f32 { ... }
    fn adjust_estimate_with_zeros(
        raw_estimate: f32,
        number_of_zeros: usize,
    ) -> f32 { ... }
    fn use_small_range_correction(&self) -> bool { ... }
    fn estimate_cardinality(&self) -> f32 { ... }
    fn estimate_union_cardinality(&self, other: &Self) -> f32 { ... }
    fn estimate_union_and_sets_cardinality<F: Primitive<f32> + MaxMin>(
        &self,
        other: &Self,
    ) -> EstimatedUnionCardinalities<F> { ... }
    fn estimate_intersection_cardinality<F: Primitive<f32>>(
        &self,
        other: &Self,
    ) -> F { ... }
    fn estimate_jaccard_index(&self, other: &Self) -> f32 { ... }
    fn estimate_difference_cardinality<F: Primitive<f32> + One>(
        &self,
        other: &Self,
    ) -> F { ... }
    fn len(&self) -> usize { ... }
    fn is_empty(&self) -> bool { ... }
    fn get_number_of_padding_registers() -> usize { ... }
    fn get_number_of_non_zero_registers(&self) -> usize { ... }
    fn get_registers(&self) -> P::Registers { ... }
    fn may_contain<T: Hash>(&self, rhs: &T) -> bool { ... }
    fn may_contain_all(&self, rhs: &Self) -> bool { ... }
    fn get_hash_and_index<T: Hash>(&self, value: &T) -> (u64, usize) { ... }
    fn estimate_cardinality_from_multiplicities(
        multiplicities: &P::RegisterMultiplicities,
    ) -> f32 { ... }
}

Provided Associated Constants

const INTERMEDIATE_RANGE_CORRECTION_THRESHOLD: f32 = _

The threshold value used in the small range correction of the HyperLogLog algorithm.

const LINEAR_COUNT_THRESHOLD: f32 = _

const LOWER_REGISTER_MASK: u32 = _

The mask used to obtain the lower register bits in the HyperLogLog algorithm.

const LOWER_PRECISION_MASK: usize = _

The mask used to obtain the lower precision bits in the HyperLogLog algorithm.

const NOT_LOWER_PRECISION_MASK: u64 = _

const NUMBER_OF_PADDING_BITS: usize = _

const PADDING_BITS_MASK: u32 = _

The mask representing the bits that are never used in the u32 word in the cases where the number of bits is not a divisor of 32, such as 5 or 6. We set the LEADING bits as the padding bits, the unused one, so the leftmost bits.

const NUMBER_OF_PADDING_REGISTERS: usize = _

const LAST_WORD_PADDING_BITS_MASK: u32 = _

The mask representing the bits that are never used in the last u32 word in the cases where the number of registers is not a multiple of the number of registers in a word.

const UPPER_PRECISION_MASK: usize = _

The mask used to obtain the upper precision bits in the HyperLogLog algorithm.

const NUMBER_OF_REGISTERS_IN_WORD: usize = _

The number of registers that can fit in a single 32-bit word in the HyperLogLog algorithm.

Required Methods

fn get_number_of_zero_registers(&self) -> usize

Returns the number of registers with zero values. This value is used for computing a small correction when estimating the cardinality of a small set.

Examples

// Create a new HyperLogLog counter with precision 14 and 5 bits per register.
let mut hll = HyperLogLog::<Precision14, 5>::default();

// Add some elements to the counter.
hll.insert(&1);
hll.insert(&2);
hll.insert(&3);

// Get the number of zero registers.
let number_of_zero_registers = hll.get_number_of_zero_registers();

assert_eq!(number_of_zero_registers, 16381);

fn get_words(&self) -> &P::Words

Returns the array of words of the HyperLogLog counter.

Provided Methods

fn adjust_estimate(raw_estimate: f32) -> f32

fn adjust_estimate_with_zeros(raw_estimate: f32, number_of_zeros: usize) -> f32

fn use_small_range_correction(&self) -> bool

Returns whether the cardinality of this HLL will be computed using the small-range correction.

Implementation details

The small-range correction is used when the cardinality of the set is small enough that the linear counting algorithm can be used to estimate the cardinality. The threshold for using the linear counting algorithm is determined by the number of registers in the HLL counter.

fn estimate_cardinality(&self) -> f32

Estimates the cardinality of the set based on the HLL counter data.

Example

let mut hll = HyperLogLog::<Precision9, 5>::default();
let elements = vec![1, 2, 3, 4, 5];
for element in &elements {
    hll.insert(element);
}
let estimated_cardinality = hll.estimate_cardinality();
assert!(estimated_cardinality >= elements.len() as f32 * 0.9 &&
        estimated_cardinality <= elements.len() as f32 * 1.1);

Returns

• f32 - The estimated cardinality of the set.

fn estimate_union_cardinality(&self, other: &Self) -> f32

Returns an estimate of the cardinality of the union of two HyperLogLog counters.

This method calculates an estimate of the cardinality of the union of two HyperLogLog counters using the raw estimation values of each counter. It combines the estimation values by iterating over the register words of both counters and performing necessary calculations.

Arguments

• other: A reference to the other HyperLogLog counter.

Returns

An estimation of the cardinality of the union of the two HyperLogLog counters.

Example

use hyperloglog_rs::prelude::*;

let mut hll1 = HyperLogLog::<Precision12, 6>::default();
hll1.insert(&1);
hll1.insert(&2);

let mut hll2 = HyperLogLog::<Precision12, 6>::default();
hll2.insert(&2);
hll2.insert(&3);

let union_cardinality = hll1.estimate_union_cardinality(&hll2);

assert!(union_cardinality >= 3.0 * 0.9 &&
        union_cardinality <= 3.0 * 1.1);

fn estimate_union_and_sets_cardinality<F: Primitive<f32> + MaxMin>( &self, other: &Self, ) -> EstimatedUnionCardinalities<F>

Returns an estimate of the cardinality of the two HLL counters union.

fn estimate_intersection_cardinality<F: Primitive<f32>>( &self, other: &Self, ) -> F

Returns an estimate of the cardinality of the intersection of two HyperLogLog counters.

This method calculates an estimate of the cardinality of the intersection of two HyperLogLog counters using the raw estimation values of each counter. It combines the estimation values by iterating over the register words of both counters and performing necessary calculations.

Arguments

• other: A reference to the other HyperLogLog counter.

Returns

An estimation of the cardinality of the intersection of the two HyperLogLog counters.

Example

use hyperloglog_rs::prelude::*;

let mut hll1 = HyperLogLog::<Precision12, 6>::default();
hll1.insert(&1);
hll1.insert(&2);

let mut hll2 = HyperLogLog::<Precision12, 6>::default();
hll2.insert(&2);
hll2.insert(&3);

let intersection_cardinality: f32 = hll1.estimate_intersection_cardinality(&hll2);

assert!(intersection_cardinality >= 1.0 * 0.9 &&
        intersection_cardinality <= 1.0 * 1.1);

fn estimate_jaccard_index(&self, other: &Self) -> f32

Returns an estimate of the Jaccard index between two HyperLogLog counters.

The Jaccard index is a measure of similarity between two sets. In the context of HyperLogLog counters, it represents the ratio of the size of the intersection of the sets represented by the counters to the size of their union. This method estimates the Jaccard index by utilizing the cardinality estimation values of the intersection, left set, and right set.

Arguments

• other: A reference to the other HyperLogLog counter.

Returns

An estimation of the Jaccard index between the two HyperLogLog counters.

Example

use hyperloglog_rs::prelude::*;

let mut hll1 = HyperLogLog::<Precision12, 6>::default();
hll1.insert(&1);
hll1.insert(&2);
hll1.insert(&3);
hll1.insert(&4);

let mut hll2 = HyperLogLog::<Precision12, 6>::default();
hll2.insert(&2);
hll2.insert(&3);
hll2.insert(&5);
hll2.insert(&6);

let jaccard_index = hll1.estimate_jaccard_index(&hll2);

let expected = 2.0 / 6.0;

assert!(jaccard_index >= expected * 0.9 &&
        jaccard_index <= expected * 1.1);

fn estimate_difference_cardinality<F: Primitive<f32> + One>( &self, other: &Self, ) -> F

Returns an estimate of the cardinality of the current HyperLogLog counter minus the provided one.

Arguments

• other: A reference to the other HyperLogLog counter.

Example

use hyperloglog_rs::prelude::*;

let mut hll1 = HyperLogLog::<Precision12, 6>::default();
hll1.insert(&1);
hll1.insert(&2);
hll1.insert(&3);
hll1.insert(&4);
     
let mut hll2 = HyperLogLog::<Precision12, 6>::default();
hll2.insert(&2);
hll2.insert(&3);
hll2.insert(&5);
hll2.insert(&6);

let difference_cardinality: f32 = hll1.estimate_difference_cardinality(&hll2);

assert!(difference_cardinality >= 2.0 * 0.9 &&
       difference_cardinality <= 2.0 * 1.1);

fn len(&self) -> usize

Returns the number of registers in the HLL counter.

Example

// Create a new HLL counter with 128 registers
let mut hll = HyperLogLog::<Precision12, 4>::default();
assert_eq!(hll.len(), 4096);

// Insert some elements into the HLL counter
hll.insert(&1);
hll.insert(&2);
hll.insert(&3);
assert_eq!(hll.len(), 1 << 12);

// Merge another HLL counter with 128 registers
let mut hll2 = HyperLogLog::<Precision12, 4>::default();
hll2.insert(&4);
hll2.insert(&5);
hll |= hll2;
assert_eq!(hll.len(), 1 << 12);

fn is_empty(&self) -> bool

Returns whether no element was yet added to the HLL counter.

Examples

use hyperloglog_rs::prelude::*;

let mut hll: HyperLogLog<Precision8, 4> = HyperLogLog::default();

assert!(hll.is_empty());

hll.insert(&1);

assert!(!hll.is_empty());

fn get_number_of_padding_registers() -> usize

Returns the number of extra registers that are not actually used.

Examples

Since the number of registers is not a multiple of the number of registers in a word, there are padding registers that are not actually used.

assert_eq!(HyperLogLog::<Precision10, 6>::get_number_of_padding_registers(), 1);

For instance, in the case using the bare minimum bits per registers (4) and the minimal precision (4), for a total of 16 registers, we expect to not have any padding registers.

assert_eq!(HyperLogLog::<Precision4, 1>::get_number_of_padding_registers(), 16, "Expected 16 padding registers, precision 4, bits 1, got {}.", HyperLogLog::<Precision4, 1>::get_number_of_padding_registers());
assert_eq!(HyperLogLog::<Precision4, 2>::get_number_of_padding_registers(), 0, "Expected 0 padding registers, precision 4, bits 2, got {}.", HyperLogLog::<Precision4, 2>::get_number_of_padding_registers());
assert_eq!(HyperLogLog::<Precision4, 3>::get_number_of_padding_registers(), 4, "Expected 4 padding registers, precision 4, bits 3, got {}.", HyperLogLog::<Precision4, 3>::get_number_of_padding_registers());
assert_eq!(HyperLogLog::<Precision4, 4>::get_number_of_padding_registers(), 0, "Expected 0 padding registers, precision 4, bits 4, got {}.", HyperLogLog::<Precision4, 4>::get_number_of_padding_registers());
assert_eq!(HyperLogLog::<Precision4, 5>::get_number_of_padding_registers(), 2, "Expected 2 padding registers, precision 4, bits 5, got {}.", HyperLogLog::<Precision4, 5>::get_number_of_padding_registers());
assert_eq!(HyperLogLog::<Precision4, 6>::get_number_of_padding_registers(), 4, "Expected 1 padding registers, precision 4, bits 6, got {}.", HyperLogLog::<Precision4, 6>::get_number_of_padding_registers());

assert_eq!(HyperLogLog::<Precision5, 1>::get_number_of_padding_registers(), 0, "Expected 0 padding registers, precision 5, bits 1, got {}.", HyperLogLog::<Precision5, 1>::get_number_of_padding_registers());
assert_eq!(HyperLogLog::<Precision5, 2>::get_number_of_padding_registers(), 0, "Expected 0 padding registers, precision 5, bits 2, got {}.", HyperLogLog::<Precision5, 2>::get_number_of_padding_registers());
assert_eq!(HyperLogLog::<Precision5, 3>::get_number_of_padding_registers(), 8, "Expected 30 padding registers, precision 5, bits 3, got {}.", HyperLogLog::<Precision5, 3>::get_number_of_padding_registers());
assert_eq!(HyperLogLog::<Precision5, 4>::get_number_of_padding_registers(), 0, "Expected 0 padding registers, precision 5, bits 4, got {}.", HyperLogLog::<Precision5, 4>::get_number_of_padding_registers());
assert_eq!(HyperLogLog::<Precision5, 5>::get_number_of_padding_registers(), 4, "Expected 4 padding registers, precision 5, bits 5, got {}.", HyperLogLog::<Precision5, 5>::get_number_of_padding_registers());
assert_eq!(HyperLogLog::<Precision5, 6>::get_number_of_padding_registers(), 3, "Expected 3 padding registers, precision 5, bits 6, got {}.", HyperLogLog::<Precision5, 6>::get_number_of_padding_registers());

assert_eq!(HyperLogLog::<Precision6, 1>::get_number_of_padding_registers(), 0, "Expected 0 padding registers, precision 6, bits 1, got {}.", HyperLogLog::<Precision6, 1>::get_number_of_padding_registers());
assert_eq!(HyperLogLog::<Precision6, 2>::get_number_of_padding_registers(), 0, "Expected 0 padding registers, precision 6, bits 2, got {}.", HyperLogLog::<Precision6, 2>::get_number_of_padding_registers());
assert_eq!(HyperLogLog::<Precision6, 3>::get_number_of_padding_registers(), 6, "Expected 6 padding registers, precision 6, bits 3, got {}.", HyperLogLog::<Precision6, 3>::get_number_of_padding_registers());
assert_eq!(HyperLogLog::<Precision6, 4>::get_number_of_padding_registers(), 0, "Expected 0 padding registers, precision 6, bits 4, got {}.", HyperLogLog::<Precision6, 4>::get_number_of_padding_registers());
assert_eq!(HyperLogLog::<Precision6, 5>::get_number_of_padding_registers(), 2, "Expected 2 padding registers, precision 6, bits 5, got {}.", HyperLogLog::<Precision6, 5>::get_number_of_padding_registers());
assert_eq!(HyperLogLog::<Precision6, 6>::get_number_of_padding_registers(), 1, "Expected 1 padding registers, precision 6, bits 6, got {}.", HyperLogLog::<Precision6, 6>::get_number_of_padding_registers());

fn get_number_of_non_zero_registers(&self) -> usize

fn get_registers(&self) -> P::Registers

Returns an array of registers of the HyperLogLog counter.

Examples

let mut hll = HyperLogLog::<Precision10, 6>::default();
hll.insert(&4);
hll.insert(&5);
hll.insert(&6);
let registers = hll.get_registers();

assert_eq!(registers.len(), 1024);
assert!(registers.iter().any(|&x| x > 0));

We can also create an HLL from registers, and then check whether the registers are what we expect:

let expected = [3, 2, 1, 1, 7, 15, 39, 63, 28, 23, 0, 0, 11, 11, 11, 0];
let mut hll = HyperLogLog::<Precision4, 6>::from_registers(&expected);
assert_eq!(hll.get_registers(), expected, "Expected {:?}, got {:?}", expected, hll.get_registers());

fn may_contain<T: Hash>(&self, rhs: &T) -> bool

Returns true if the HyperLogLog counter may contain the given element.

Arguments

• rhs - The element to check.

Examples

let mut hll: HyperLogLog<Precision8, 6> = HyperLogLog::default();
assert_eq!(hll.may_contain(&42), false);

hll.insert(&42);
assert_eq!(hll.may_contain(&42), true);

fn may_contain_all(&self, rhs: &Self) -> bool

Returns whether the provided HyperLogLog counter may be fully contained in the current HyperLogLog counter.

Arguments

• rhs - The HyperLogLog counter to check.

Implementative details

We define a counter that fully contains another counter when all of the registers of the first counter are greater than or equal to the corresponding registers of the second counter.

Examples

let mut hll1: HyperLogLog<Precision8, 6> = HyperLogLog::default();
let mut hll2: HyperLogLog<Precision8, 6> = HyperLogLog::default();

hll1.insert(&42);
hll1.insert(&43);
hll1.insert(&44);

hll2.insert(&42);
hll2.insert(&43);

assert_eq!(hll1.may_contain_all(&hll2), true);
assert_eq!(hll2.may_contain_all(&hll1), false);

hll2.insert(&44);

assert_eq!(hll1.may_contain_all(&hll2), true);
assert_eq!(hll2.may_contain_all(&hll1), true);

fn get_hash_and_index<T: Hash>(&self, value: &T) -> (u64, usize)

Returns the hash value and the corresponding register’s index for a given value.

Arguments

• value - A reference to the value to be hashed.

Examples

use hyperloglog_rs::prelude::*;

let mut hll: HyperLogLog<Precision8, 6> = HyperLogLog::default();
let value = 42;
let (hash, index) = hll.get_hash_and_index(&value);

//assert_eq!(hash, 10123147082338939904, "Expected hash {}, got {}.", 10123147082338939904, hash);

fn estimate_cardinality_from_multiplicities( multiplicities: &P::RegisterMultiplicities, ) -> f32

Returns the number of registers in the counter.

Implementation details

This function is overriding the estimate_cardinality function of the HyperLogLogTrait trait as we can compute the cardinality of the counter using the multiplicities instead of the registers. This is much faster as we do not need to compute the harmonic mean of the registers.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<P: Precision + WordType<BITS>, const BITS: usize> HyperLogLogTrait<P, BITS> for HyperLogLog<P, BITS>

impl<P: Precision + WordType<BITS>, const BITS: usize> HyperLogLogTrait<P, BITS> for HyperLogLogWithMultiplicities<P, BITS>