count_min_sketch< W, Allocator > Class Template Reference

C++ implementation of the CountMin sketch data structure of Cormode and Muthukrishnan. More...

#include <count_min.hpp>

Public Member Functions
	count_min_sketch (uint8_t num_hashes, uint32_t num_buckets, uint64_t seed=DEFAULT_SEED, const Allocator &allocator=Allocator())
	Creates an instance of the sketch given parameters _num_hashes, _num_buckets and hash seed, seed. More...
uint8_t	get_num_hashes () const
uint32_t	get_num_buckets () const
uint64_t	get_seed () const
double	get_relative_error () const
W	get_total_weight () const
W	get_estimate (uint64_t item) const
	Specific get_estimate function for uint64_t type see generic get_estimate function. More...
W	get_estimate (int64_t item) const
	Specific get_estimate function for int64_t type see generic get_estimate function. More...
W	get_estimate (const std::string &item) const
	Specific get_estimate function for std::string type see generic get_estimate function. More...
W	get_estimate (const void *item, size_t size) const
	This is the generic estimate query function for any of the given datatypes. More...
W	get_upper_bound (const void *item, size_t size) const
	Query the sketch for the upper bound of a given item. More...
W	get_upper_bound (int64_t item) const
	Query the sketch for the upper bound of a given item. More...
W	get_upper_bound (uint64_t item) const
	Query the sketch for the upper bound of a given item. More...
W	get_upper_bound (const std::string &item) const
	Query the sketch for the upper bound of a given item. More...
W	get_lower_bound (const void *item, size_t size) const
	Query the sketch for the lower bound of a given item. More...
W	get_lower_bound (int64_t item) const
	Query the sketch for the lower bound of a given item. More...
W	get_lower_bound (uint64_t item) const
	Query the sketch for the lower bound of a given item. More...
W	get_lower_bound (const std::string &item) const
	Query the sketch for the lower bound of a given item. More...
void	update (const void *item, size_t size, W weight)
	Update this sketch with given data of any type. More...
void	update (uint64_t item, W weight=1)
	Update this sketch with a given item. More...
void	update (int64_t item, W weight=1)
	Update this sketch with a given item. More...
void	update (const std::string &item, W weight=1)
	Update this sketch with a given string. More...
void	merge (const count_min_sketch &other_sketch)
	Merges another count_min_sketch into this count_min_sketch. More...
bool	is_empty () const
	Returns true if this sketch is empty. More...
string< Allocator >	to_string () const
	Returns a string describing the sketch. More...
const_iterator	begin () const
	Iterator pointing to the first item in the sketch. More...
const_iterator	end () const
	Iterator pointing to the past-the-end item in the sketch. More...
size_t	get_serialized_size_bytes () const
	Computes size needed to serialize the current state of the sketch. More...
void	serialize (std::ostream &os) const
	This method serializes the sketch into a given stream in a binary form. More...
vector_bytes	serialize (unsigned header_size_bytes=0) const
	This method serializes the sketch as a vector of bytes. More...
allocator_type	get_allocator () const

Static Public Member Functions
static uint32_t	suggest_num_buckets (double relative_error)
	Suggests the number of buckets required to achieve the given relative error. More...
static uint8_t	suggest_num_hashes (double confidence)
	Suggests the number of hash functions required to achieve the given confidence. More...
static count_min_sketch	deserialize (std::istream &is, uint64_t seed=DEFAULT_SEED, const Allocator &allocator=Allocator())
	This method deserializes a sketch from a given stream. More...
static count_min_sketch	deserialize (const void *bytes, size_t size, uint64_t seed=DEFAULT_SEED, const Allocator &allocator=Allocator())
	This method deserializes a sketch from a given array of bytes. More...

Detailed Description

template<typename W, typename Allocator = std::allocator<W>>
class datasketches::count_min_sketch< W, Allocator >

C++ implementation of the CountMin sketch data structure of Cormode and Muthukrishnan.

[1] - http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf The template type W is the type of the vector that contains the weights of the objects inserted into the sketch, not the type of the input items themselves.

Author

Charlie Dickens

Constructor & Destructor Documentation

count_min_sketch()

count_min_sketch	(	uint8_t	num_hashes,
		uint32_t	num_buckets,
		uint64_t	seed = DEFAULT_SEED,
		const Allocator &	allocator = Allocator()
	)

Creates an instance of the sketch given parameters _num_hashes, _num_buckets and hash seed, seed.

Parameters

num_hashes	number of hash functions in the sketch. Equivalently the number of rows in the array
num_buckets	number of buckets that hash functions map into. Equivalently the number of columns in the array
seed	for hash function
allocator	to acquire and release memory

The items inserted into the sketch can be arbitrary type, so long as they are hashable via murmurhash. Only update and estimate methods are added for uint64_t and string types.

Member Function Documentation

get_num_hashes()

uint8_t get_num_hashes

Returns

configured _num_hashes of this sketch

get_num_buckets()

uint32_t get_num_buckets

Returns

configured _num_buckets of this sketch

get_seed()

uint64_t get_seed

Returns

configured seed of this sketch

get_relative_error()

double get_relative_error

Returns

epsilon The maximum permissible error for any frequency estimate query. epsilon = ceil(e / _num_buckets)

get_total_weight()

W get_total_weight

Returns

_total_weight The total weight currently inserted into the stream.

suggest_num_buckets()

uint32_t suggest_num_buckets ( double  relative_error )

static

Suggests the number of buckets required to achieve the given relative error.

Parameters

relative_error

the desired accuracy within which estimates should lie. For example, when relative_error = 0.05, then the returned frequency estimates satisfy the relative_error guarantee that never overestimates the weights but may underestimate the weights by 5% of the total weight in the sketch.

Returns

the number of hash buckets at every level of the sketch required in order to obtain the specified relative error. [1] - Section 3 `‘Data Structure’', page 6.

suggest_num_hashes()

uint8_t suggest_num_hashes ( double  confidence )

static

Suggests the number of hash functions required to achieve the given confidence.

Parameters

confidence

the desired confidence with which estimates should be correct. For example, with 95% confidence, frequency estimates satisfy the relative_error guarantee.

Returns

the number of hash functions that are required in order to achieve the specified confidence of the sketch. confidence = 1 - delta, with delta denoting the sketch failure probability in the literature. [1] - Section 3 `‘Data Structure’', page 6.

get_estimate() [1/4]

W get_estimate

(

uint64_t

item

)

const

Specific get_estimate function for uint64_t type see generic get_estimate function.

Parameters

item	uint64_t type.

Returns

an estimate of the item's frequency.

get_estimate() [2/4]

W get_estimate

(

int64_t

item

)

const

Specific get_estimate function for int64_t type see generic get_estimate function.

Parameters

item	int64_t type.

Returns

an estimate of the item's frequency.

get_estimate() [3/4]

W get_estimate

(

const std::string &

item

)

const

Specific get_estimate function for std::string type see generic get_estimate function.

Parameters

item	std::string type

Returns

an estimate of the item's frequency.

get_estimate() [4/4]

W get_estimate	(	const void *	item,
		size_t	size
	)		const

This is the generic estimate query function for any of the given datatypes.

Query the sketch for the estimate of a given item.

Parameters

item	pointer to the data item to be query from the sketch.
size	size of the item in bytes

Returns

the estimated frequency of the item denoted f_est satisfying f_true - relative_error*_total_weight <= f_est <= f_true

get_upper_bound() [1/4]

W get_upper_bound	(	const void *	item,
		size_t	size
	)		const

Query the sketch for the upper bound of a given item.

Parameters

item	to query
size	of the item in bytes

Returns

the upper bound on the true frequency of the item f_true <= f_est + relative_error*_total_weight

get_upper_bound() [2/4]

W get_upper_bound

(

int64_t

item

)

const

Query the sketch for the upper bound of a given item.

Parameters

item

to query

Returns

the upper bound on the true frequency of the item f_true <= f_est + relative_error*_total_weight

get_upper_bound() [3/4]

W get_upper_bound

(

uint64_t

item

)

const

Query the sketch for the upper bound of a given item.

Parameters

item

to query

Returns

the upper bound on the true frequency of the item f_true <= f_est + relative_error*_total_weight

get_upper_bound() [4/4]

W get_upper_bound

(

const std::string &

item

)

const

Query the sketch for the upper bound of a given item.

Parameters

item

to query

Returns

the upper bound on the true frequency of the item f_true <= f_est + relative_error*_total_weight

get_lower_bound() [1/4]

W get_lower_bound	(	const void *	item,
		size_t	size
	)		const

Query the sketch for the lower bound of a given item.

Parameters

item	to query
size	of the item in bytes

Returns

the lower bound for the query result, f_est, on the true frequency, f_est of the item f_true - relative_error*_total_weight <= f_est

get_lower_bound() [2/4]

W get_lower_bound

(

int64_t

item

)

const

Query the sketch for the lower bound of a given item.

Parameters

item

to query

Returns

the lower bound for the query result, f_est, on the true frequency, f_est of the item f_true - relative_error*_total_weight <= f_est

get_lower_bound() [3/4]

W get_lower_bound

(

uint64_t

item

)

const

Query the sketch for the lower bound of a given item.

Parameters

item

to query

Returns

the lower bound for the query result, f_est, on the true frequency, f_est of the item f_true - relative_error*_total_weight <= f_est

get_lower_bound() [4/4]

W get_lower_bound

(

const std::string &

item

)

const

Query the sketch for the lower bound of a given item.

Parameters

item

to query

Returns

the lower bound for the query result, f_est, on the true frequency, f_est of the item f_true - relative_error*_total_weight <= f_est

update() [1/4]

void update	(	const void *	item,
		size_t	size,
		W	weight
	)

Update this sketch with given data of any type.

This is a "universal" update that covers all cases, but may produce different hashes compared to specialized update methods.

Parameters

item	pointer to the data item to be inserted into the sketch.
size	of the data in bytes
weight	arithmetic type

update() [2/4]

void update	(	uint64_t	item,
		W	weight = 1
	)

Update this sketch with a given item.

Parameters

item	to update the sketch with
weight	arithmetic type

update() [3/4]

void update	(	int64_t	item,
		W	weight = 1
	)

Update this sketch with a given item.

Parameters

item	to update the sketch with
weight	arithmetic type

update() [4/4]

void update	(	const std::string &	item,
		W	weight = 1
	)

Update this sketch with a given string.

Parameters

item	string to update the sketch with
weight	arithmetic type

merge()

void merge

(

const count_min_sketch< W, Allocator > &

other_sketch

)

Merges another count_min_sketch into this count_min_sketch.

Parameters

other_sketch

is_empty()

bool is_empty

Returns true if this sketch is empty.

A Count Min Sketch is defined to be empty iff weight == 0 This can only ever happen if all items inserted to the sketch have weights that cancel each other out.

Returns

empty flag

to_string()

string< A > to_string

Returns a string describing the sketch.

Returns

A string with a human-readable description of the sketch

begin()

count_min_sketch< W, A >::const_iterator begin

Iterator pointing to the first item in the sketch.

If the sketch is empty, the returned iterator must not be dereferenced or incremented.

Returns

iterator pointing to the first item in the sketch

end()

count_min_sketch< W, A >::const_iterator end

Iterator pointing to the past-the-end item in the sketch.

The past-the-end item is the hypothetical item that would follow the last item. It does not point to any item, and must not be dereferenced or incremented.

Returns

iterator pointing to the past-the-end item in the sketch

get_serialized_size_bytes()

size_t get_serialized_size_bytes

Computes size needed to serialize the current state of the sketch.

Returns

size in bytes needed to serialize this sketch

serialize() [1/2]

void serialize

(

std::ostream &

os

)

const

This method serializes the sketch into a given stream in a binary form.

Parameters

os	output stream

serialize() [2/2]

auto serialize

(

unsigned

header_size_bytes = 0

)

const

This method serializes the sketch as a vector of bytes.

An optional header can be reserved in front of the sketch. It is an uninitialized space of a given size. This header is used in Datasketches PostgreSQL extension.

Parameters

header_size_bytes

space to reserve in front of the sketch

deserialize() [1/2]

static count_min_sketch deserialize ( std::istream &  is, uint64_t  seed = DEFAULT_SEED, const Allocator &  allocator = Allocator()  )

static

This method deserializes a sketch from a given stream.

Parameters

is	input stream
seed	the seed for the hash function that was used to create the sketch
allocator	instance of an Allocator

Returns

an instance of a sketch

deserialize() [2/2]

static count_min_sketch deserialize ( const void *  bytes, size_t  size, uint64_t  seed = DEFAULT_SEED, const Allocator &  allocator = Allocator()  )

static

This method deserializes a sketch from a given array of bytes.

Parameters

bytes	pointer to the array of bytes
size	the size of the array
seed	the seed for the hash function that was used to create the sketch
allocator	instance of an Allocator

Returns

an instance of the sketch

get_allocator()

allocator_type get_allocator

(

)

const

Returns

allocator

---

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

• count/include/count_min.hpp
• count/include/count_min_impl.hpp