Count-Min Sketch frequency estimator. More...

#include <count-min-sketch.H>

Collaboration diagram for Aleph::Count_Min_Sketch< T, CounterT >:

Public Member Functions
	Count_Min_Sketch (const size_t w, const size_t d)
	Construct with explicit dimensions.

void	update (const T &val, CounterT count=1)
	Increment count for an element.

CounterT	estimate (const T &val) const
	Estimate frequency of an element.

void	merge (const Count_Min_Sketch &other)
	Merge another sketch into this one.

void	clear ()
	Clear all counters.

size_t	width () const noexcept
	Number of counter columns (hash buckets per row).

size_t	depth () const noexcept
	Number of hash functions (independent counter rows).

CounterT	total_count () const noexcept
	Sum of all event weights inserted so far.

Static Public Member Functions
static Count_Min_Sketch	from_error_bounds (const double epsilon, const double delta)
	Create a sketch with target error bounds.

Private Attributes
size_t	w_
	Width of the sketch.

size_t	d_
	Depth (number of hash functions).

Array< CounterT >	table_
	Flat array for counters [d_ x w_].

Array< uint32_t >	seeds_
	Random seeds for hash functions.

CounterT	total_count_ = 0
	Total updates processed.

Detailed Description

template<typename T, std::unsigned_integral CounterT = size_t>
class Aleph::Count_Min_Sketch< T, CounterT >

Count-Min Sketch frequency estimator.

Provides approximate frequency queries for elements in a stream. The estimate is always an upper bound (no false negatives).

Memory complexity is O(w * d), where:

w = width (related to error magnitude)
d = depth (related to confidence)

Template Parameters

T	Type of elements to count.
CounterT	Unsigned integral type for counters (default: size_t).

Definition at line 70 of file count-min-sketch.H.

Constructor & Destructor Documentation

◆ Count_Min_Sketch()

template<typename T , std::unsigned_integral CounterT = size_t>

Aleph::Count_Min_Sketch< T, CounterT >::Count_Min_Sketch	(	const size_t	w,
		const size_t	d
	)

inline

Construct with explicit dimensions.

Parameters

[in]	w	Width (columns).
[in]	d	Depth (rows / hash functions).

Definition at line 83 of file count-min-sketch.H.

References ah_domain_error_if, Aleph::Array< T >::append(), Aleph::Count_Min_Sketch< T, CounterT >::d_, Aleph::dft_hash_fct(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::reserve(), Aleph::Count_Min_Sketch< T, CounterT >::seeds_, Aleph::Count_Min_Sketch< T, CounterT >::table_, w, and Aleph::Count_Min_Sketch< T, CounterT >::w_.

Member Function Documentation

◆ clear()

template<typename T , std::unsigned_integral CounterT = size_t>

void Aleph::Count_Min_Sketch< T, CounterT >::clear ( )

inline

Clear all counters.

Definition at line 196 of file count-min-sketch.H.

References Aleph::Count_Min_Sketch< T, CounterT >::table_, and Aleph::Count_Min_Sketch< T, CounterT >::total_count_.

◆ depth()

template<typename T , std::unsigned_integral CounterT = size_t>

size_t Aleph::Count_Min_Sketch< T, CounterT >::depth ( ) const

inlinenoexcept

Number of hash functions (independent counter rows).

Returns: size_t The depth d passed at construction.

Exceptions

none

Note: Complexity: O(1).

Definition at line 215 of file count-min-sketch.H.

References Aleph::Count_Min_Sketch< T, CounterT >::d_.

◆ estimate()

template<typename T , std::unsigned_integral CounterT = size_t>

CounterT Aleph::Count_Min_Sketch< T, CounterT >::estimate ( const T & val ) const

inline

Estimate frequency of an element.

Returns: Approximate frequency (always >= actual).

Definition at line 156 of file count-min-sketch.H.

References Aleph::Count_Min_Sketch< T, CounterT >::d_, Aleph::divide_and_conquer_partition_dp(), h, Aleph::murmur3hash(), Aleph::Count_Min_Sketch< T, CounterT >::seeds_, Aleph::Count_Min_Sketch< T, CounterT >::table_, and Aleph::Count_Min_Sketch< T, CounterT >::w_.

◆ from_error_bounds()

template<typename T , std::unsigned_integral CounterT = size_t>

static Count_Min_Sketch Aleph::Count_Min_Sketch< T, CounterT >::from_error_bounds	(	const double	epsilon,
		const double	delta
	)

inlinestatic

Create a sketch with target error bounds.

Calculates optimal w and d for given epsilon and delta. Estimate will be within epsilon * total_count from actual with probability at least 1 - delta.

Parameters