Struct pdatastructs::CountMinSketch

pub struct CountMinSketch<C = usize> where
    C: Counter,  { /* fields omitted */ }

Simple implementation of a Count-min sketch

The type parameter C sets the type of the counter in the internal table and can be used to reduce memory consumption when low counts are expected.

Methods

impl<C> CountMinSketch<C> where
    C: Counter, 

fn with_params(w: usize, d: usize) -> CountMinSketch<C>

Create new CountMinSketch based on table size.

• w sets the number of columns
• d sets the number of rows

fn with_point_query_properties(epsilon: f64, delta: f64) -> CountMinSketch<C>

Create new CountMinSketch with the following properties for a point query:

• a is the real count of observed objects
• a' is the guessed count of observed objects
• N is the total count in the internal table
• a <= a' always holds
• a' <= a + epsilon * N holds with p > 1 - delta

The following conditions must hold:

• epsilon > 0
• delta > 0 and delta < 1

Panics when the input conditions do not hold.

fn w(&self) -> usize

Get number of columns of internal counter table.

fn d(&self) -> usize

Get number of rows of internal counter table.

fn is_empty(&self) -> bool

Check whether the CountMinSketch is empty (i.e. no elements seen yet).

fn add<T>(&mut self, obj: &T) where
    T: Hash, 

Add one to the counter of the given element.

fn add_n<T>(&mut self, obj: &T, n: C) where
    T: Hash, 

Add n to the counter of the given element.

fn query_point<T>(&self, obj: &T) -> C where
    T: Hash, 

Runs a point query, i.e. a query for the count of a single object.

fn merge(&mut self, other: &CountMinSketch<C>)

Merge self with another CountMinSketch.

After this operation self will be in the same state as when it would have seen all elements from self and other.

Panics when d and w from self and other differ.

fn clear(&mut self)

Clear internal counters to a fresh state (i.e. no objects seen).

Trait Implementations

impl<C: Clone> Clone for CountMinSketch<C> where
    C: Counter, 

fn clone(&self) -> CountMinSketch<C>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for CountMinSketch

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

Formats the value using the given formatter.