turi::sketches::countsketch< T > Class Template Reference

#include <ml/sketches/countsketch.hpp>

Public Member Functions
	countsketch (size_t bits=16, size_t depth=5, size_t seed=1000)
	Buckets. More...
void	add (const T &t, size_t count=1)
counter_int	estimate (const T &t)
void	combine (const countsketch &other)
void	print ()
double	density ()

Detailed Description

template<typename T>
class turi::sketches::countsketch< T >

An implementation of the CountSketch for estimating the frequency of each item in a stream.

Usage is simple.

countsketch<T> c; // for approximate counting of a stream with type T
// repeatedly call
c.add(x)      // x can be anything that is hashable.
c.estimate(x) // will return an estimate of the frequency for
              // a given element

Definition at line 35 of file countsketch.hpp.

Constructor & Destructor Documentation

countsketch()

template<typename T >

turi::sketches::countsketch< T >::countsketch ( size_t  bits = 16, size_t  depth = 5, size_t  seed = 1000  )

inlineexplicit

Buckets.

Constructs a CountSketch having "width" 2^bits and "depth". The size of the matrix of counts will be depth x 2^bits.

Parameters

bits	The number of bins will be 2^bits.
depth	The "depth" of the sketch is the number of hash functions that will be used on each item.

Definition at line 57 of file countsketch.hpp.

Member Function Documentation

add()

template<typename T >

void turi::sketches::countsketch< T >::add ( const T &  t, size_t  count = 1  )

inline

Adds an arbitrary object to be counted. Any object type can be used, and there are no restrictions as long as std::hash<T> can be used to obtain a hash value.

Note: Theoretical properties only apply to the situation where count is 1.

Definition at line 80 of file countsketch.hpp.

combine()

template<typename T >

void turi::sketches::countsketch< T >::combine ( const countsketch< T > &  other )

inline

Merge two CountSketch datastructures. The two countsketch objects must have the same width and depth.

Definition at line 127 of file countsketch.hpp.

density()

template<typename T >

double turi::sketches::countsketch< T >::density ( )

inline

Computes the density of the internal counts matrix.

Definition at line 156 of file countsketch.hpp.

estimate()

template<typename T >

counter_int turi::sketches::countsketch< T >::estimate ( const T &  t )

inline

Returns the estimate of the frequency for a given object.

Definition at line 98 of file countsketch.hpp.

print()

template<typename T >

void turi::sketches::countsketch< T >::print ( )

inline

Prints the internal matrix containing the current counts.

Definition at line 143 of file countsketch.hpp.

---

The documentation for this class was generated from the following file:

• ml/sketches/countsketch.hpp