OmniSketch::Sketch::CounterHierarchy< no_layer, T, hash_t > Class Template Reference

Use the counter hierarchy to better save space while preserving accuracy! More...

#include <hierarchy.h>

Public Member Functions
	CounterHierarchy (const std::vector< size_t > &no_cnt, const std::vector< size_t > &width_cnt, const std::vector< size_t > &no_hash)
	Construct by specifying detailed architectural parameters. More...
	~CounterHierarchy ()
	Destructor. More...
void	updateCnt (size_t index, T val)
	Update a counter. More...
T	getCnt (size_t index)
	Get the value of counters in CH. More...
T	getOriginalCnt (size_t index) const
	Get the original value of counters. More...
size_t	size () const
	Size of CH. More...
size_t	originalSize () const
	Size of counters without CH. More...
void	clear ()
	Reset CH. More...

Detailed Description

template<int32_t no_layer, typename T, typename hash_t = Hash::AwareHash>
class OmniSketch::Sketch::CounterHierarchy< no_layer, T, hash_t >

Use the counter hierarchy to better save space while preserving accuracy!

Template Parameters

no_layer	Number of layers in CH
T	Counter Type of CH
hash_t	Hashing classes used internally

Note

• In CH, counters are serialized, so it is the user's job to convert the index of a possibly multi-dimensional array into a unique serial number. Since CH uses 0-based array internally, this serial number is chosen to have type size_t.
• CH uses lazy update policy. That is, only when you try to get a counter value in CH will the updates genuinely be propagated to the higher layers and then decoded.
• Note that CH cannot bring better accuracy. Ideally, if the first layer in CH never overflows, your sketch achieves the same accuracy as does without it.

Warning

• To apply CH, make sure values of the original counters are always non-negative during the whole process, though negative update is OK. (i.e., only cash register case and the non-negative case in turnstile model are allowed) Otherwise, errors of decoding can be unbounded.
• It is highly recommended that on each layer the number of counters is prime.

Constructor & Destructor Documentation

CounterHierarchy()

template<int32_t no_layer, typename T , typename hash_t >

OmniSketch::Sketch::CounterHierarchy< no_layer, T, hash_t >::CounterHierarchy	(	const std::vector< size_t > &	no_cnt,
		const std::vector< size_t > &	width_cnt,
		const std::vector< size_t > &	no_hash
	)

Construct by specifying detailed architectural parameters.

Parameters

no_cnt	number of counters on each layer, from low to high
width_cnt	width of counters on each layer, from low to high
no_hash	number of hash functions used on each layer, from low to high (except for the last layer)

The meaning of the three parameters stipulates the following requirements:

• size of no_cnt should equal no_layer.
• size of width_cnt should equal no_layer.
• size of no_hash should equal no_layer - 1.

If any of these is violated, an exception would be thrown. Other conditions that trigger an exception:

• Items in these vectors contains a 0.
• no_layer <= 0
• Sum of width_cnt exceeds sizeof(T) * 8. This constraint is imposed to guarantee proper shifting of counters when decoding.

~CounterHierarchy()

template<int32_t no_layer, typename T , typename hash_t >

OmniSketch::Sketch::CounterHierarchy< no_layer, T, hash_t >::~CounterHierarchy

Destructor.

Member Function Documentation

clear()

template<int32_t no_layer, typename T , typename hash_t >

void OmniSketch::Sketch::CounterHierarchy< no_layer, T, hash_t >::clear

Reset CH.

getCnt()

template<int32_t no_layer, typename T , typename hash_t >

T OmniSketch::Sketch::CounterHierarchy< no_layer, T, hash_t >::getCnt

(

size_t

index

)

Get the value of counters in CH.

An overflow exception would be thrown if there is an overflow at the last layer. An out-of-range exception would be thrown if the index is out of range.

Parameters

index

Serialized index of a counter. It is the user's job to get the index serialized in advance.

getOriginalCnt()

template<int32_t no_layer, typename T , typename hash_t >

T OmniSketch::Sketch::CounterHierarchy< no_layer, T, hash_t >::getOriginalCnt

(

size_t

index

)

const

Get the original value of counters.

I.e., the value of the counter without CH.

Parameters

index

Serialized index of a counter. It is the user's job to get the index serialized in advance.

originalSize()

template<int32_t no_layer, typename T , typename hash_t >

size_t OmniSketch::Sketch::CounterHierarchy< no_layer, T, hash_t >::originalSize

Size of counters without CH.

size()

template<int32_t no_layer, typename T , typename hash_t >

size_t OmniSketch::Sketch::CounterHierarchy< no_layer, T, hash_t >::size

Size of CH.

updateCnt()

template<int32_t no_layer, typename T , typename hash_t >

void OmniSketch::Sketch::CounterHierarchy< no_layer, T, hash_t >::updateCnt	(	size_t	index,
		T	val
	)

Update a counter.

Parameters

index	Serialized index of a counter. It is the user's job to get the index serialized in advance.
val	Value to be updated

Note

• Use the lazy update policy.
• An out-of-range exception would be thrown if index is out of range.