Count-Min Sketch in C++

15 May 2025 | 3 min read

Introduction:

The Count-Min Sketch is a probabilistic data structure used for approximate counting queries in large data streams. It efficiently estimates the frequency of elements in a stream of data while using limited memory space.

In essence, the Count-Min Sketch consists of a two-dimensional array of counters. Hash functions are employed to map elements of the stream to positions in this array. Multiple hash functions are typically used, each determining a different column in the array. When an element arrives in the stream, its corresponding counters in each row are incremented.

The main idea behind the Count-Min Sketch is that by using multiple hash functions and maintaining multiple counters per element, collisions are inevitable, but the minimum value across all counters for any given element tends to provide a good approximation of its true frequency. By adjusting the width and depth of the array, users can control the trade-off between accuracy and memory usage.

Program:

Output:

Count of item 42: 7
Count of item 55: 3

Explanation:

Count-Min Sketch Class: The code defines a C++ class named CountMinSketch. This class represents the Count-Min Sketch data structure.

Private Members:

width and depth: These variables represent the width and depth of the Count-Min Sketch, controlling its memory usage and accuracy.

counts: This is a two-dimensional vector representing the array of counters in the sketch.

hash_functions: This vector holds instances of the std::hash<int> function, used for hashing elements.

Constructor:

The constructor initializes the width, depth, and counts array.

It also populates the hash_functions vector with the depth number of hash functions.

Update Method:

The update method takes an item and its count as input.

It hashes the item using each hash function and updates the corresponding counters in the count's array.

Query Method:

The query method takes an item as input and returns an estimate of its count.

It hashes the item using each hash function and retrieves the minimum count across all hash functions.

Main Function:

Inside the main function, an instance of CountMinSketch is created with specified width and depth.

The sketch is updated with counts for two items: 42 and 55.

The query method is called to estimate the counts of these items, and the results are printed.

Complexity analysis:

Time Complexity:

Update Operation:

The time complexity of updating the sketch with an item's count is O(d), where ?

d is the depth of the sketch.

This is because, for each hash function (of which there are d), the update involves a constant-time operation to increment the corresponding counter.

Query Operation:

The time complexity of querying the sketch for an item's count is also O(d).

Similar to the update operation, for each hash function, the query involves accessing the corresponding counter and finding the minimum value.

Space Complexity:

The space complexity of the Count-Min Sketch is determined by the size of its data structure, which consists of:

O(w×d) space for the two-dimensional counts array, where w is the width (number of counters in each row) and d is the depth (number of hash functions).
O(d) space for storing the hash functions in the hash_functions vector.

Next TopicCheck-if-the-number-is-a-pythagorean-prime-or-not-in-cpp

← prev next →