Table of Contents

CountMinSketch<T> Class

Definition

Namespace
Bodu.Collections.Probabilistic
Assembly
Bodu.Collections.dll
Package
Bodu.Collections 1.0.0
Source
CountMinSketch{T}.cs

Represents a space-efficient probabilistic frequency sketch that estimates how many times an element has been added. Estimates can overestimate but never underestimate: EstimateCount(T) always returns at least the true count of the queried element, and with probability at least 1 − δ returns at most the true count plus ε · TotalCount.

public sealed class CountMinSketch<T> where T : notnull

Type Parameters

T

The type of elements counted by the sketch. Must not be null.

Inheritance
CountMinSketch<T>
Inherited Members
Extension Methods

Examples

// Track event frequencies with 1% additive error at 99% confidence.
var sketch = new CountMinSketch<string>(epsilon: 0.01, delta: 0.01);

sketch.Add("page-view");
sketch.Add("page-view", 41);

Console.WriteLine(sketch.EstimateCount("page-view")); // >= 42, usually exactly 42

Remarks

The sketch is sized from the constructor arguments using the standard count-min formulas: the width is w = ⌈e/ε⌉ counters per row and the depth is d = ⌈ln(1/δ)⌉ rows, where ε is Epsilon (the additive error factor) and δ is Delta (the probability of exceeding it). The counters are stored in a single flat d·w array, row-major, for cache locality across the per-row probes.

Elements are hashed via the supplied IEqualityComparer<T> (or Default): the comparer's 32-bit GetHashCode(T) is expanded through a deterministic SplitMix64-style avalanche into two 64-bit values combined by Kirsch-Mitzenmacher double hashing, one probe per row. All entropy therefore derives from the 32-bit comparer hash - standard practice for comparer-based sketches - which bounds the achievable error floor by the collision rate of that hash: two elements with equal comparer hashes share every counter.

The expansion is platform-stable, but the comparer may not be: GetHashCode() is randomized per process, so exported state for string elements (or any type with a randomized hash) is only meaningful when re-imported within the same process, or when a custom comparer with a stable hash is used.

Counts can only grow. Negative updates are not supported because a removal can drive a shared counter below another element's true count, breaking the never-underestimate guarantee that makes the minimum-over-rows estimate sound. Use Clear() to reset the entire sketch.

The export format produced by TryExport(Span<byte>, out int) / Export(Span<byte>) and consumed by Import(ReadOnlySpan<byte>, IEqualityComparer<T>?) is an opaque, version-checked snapshot, not a wire contract; its layout may change between library versions with a corresponding version-byte bump.

CountMinSketch<T> is not thread-safe. Concurrent reads and writes require external synchronization.

Constructors

CountMinSketch(double, double)

Initializes a new instance of the CountMinSketch<T> class sized for the target additive error and error probability, using the default equality comparer.

public CountMinSketch(double epsilon, double delta)

Parameters

epsilon double

The additive error factor: estimates exceed the true count by at most ε · TotalCount with probability at least 1 − δ.

delta double

The probability that an estimate exceeds the error bound.

Exceptions

ArgumentOutOfRangeException

epsilon or delta is outside the exclusive interval (0, 1), or the combination requires more than the maximum supported number of counter cells.

CountMinSketch(double, double, IEqualityComparer<T>?)

Initializes a new instance of the CountMinSketch<T> class sized for the target additive error and error probability, using the specified equality comparer.

public CountMinSketch(double epsilon, double delta, IEqualityComparer<T>? comparer)

Parameters

epsilon double

The additive error factor: estimates exceed the true count by at most ε · TotalCount with probability at least 1 − δ.

delta double

The probability that an estimate exceeds the error bound.

comparer IEqualityComparer<T>

The equality comparer whose hash codes drive counter selection. If null, the default equality comparer for T is used.

Exceptions

ArgumentOutOfRangeException

epsilon or delta is outside the exclusive interval (0, 1), or the combination requires more than the maximum supported number of counter cells.

Properties

Comparer

Gets the equality comparer whose hash codes drive counter selection.

public IEqualityComparer<T> Comparer { get; }

Property Value

IEqualityComparer<T>

The IEqualityComparer<T> instance supplied at construction, or the default comparer.

Delta

Gets the probability (δ) that an estimate exceeds the additive error bound.

public double Delta { get; }

Property Value

double

The delta constructor argument. With probability at least 1 − δ, an estimate is at most the true count plus Epsilon · TotalCount.

Depth

Gets the number of counter rows (d), one probe per row.

public int Depth { get; }

Property Value

int

The depth derived from the constructor arguments as ⌈ln(1/δ)⌉; always at least 1.

Epsilon

Gets the additive error factor (ε) the sketch was sized for.

public double Epsilon { get; }

Property Value

double

The epsilon constructor argument. Estimates exceed the true count by at most ε · TotalCount with probability at least 1 − δ.

TotalCount

Gets the running sum of all count magnitudes added to the sketch.

public long TotalCount { get; }

Property Value

long

The sum of every count passed to Add(T, long) (with Add(T) contributing 1 per call). MergeWith(CountMinSketch<T>) adds the other sketch's total; Clear() resets it to zero.

Remarks

This is the N in the error bound: an estimate exceeds the true count by at most Epsilon · TotalCount with probability at least 1 − Delta.

Width

Gets the number of counters per row (w).

public int Width { get; }

Property Value

int

The width derived from the constructor arguments as ⌈e/ε⌉; always at least 1.

Methods

Add(T)

Adds a single occurrence of an element to the sketch.

public void Add(T item)

Parameters

item T

The element to count. Must not be null.

Exceptions

ArgumentNullException

item is null.

OverflowException

A probed counter or TotalCount would exceed MaxValue.

Add(T, long)

Adds the specified number of occurrences of an element to the sketch.

public void Add(T item, long count)

Parameters

item T

The element to count. Must not be null.

count long

The number of occurrences to add.

Remarks

Only positive counts are accepted. A negative update could drive a counter shared with another element below that element's true count, breaking the never-underestimate guarantee EstimateCount(T) relies on. Use Clear() to reset the entire sketch instead.

Counter additions are checked; when an OverflowException is thrown mid-update, counters probed before the failing one retain the added count and the sketch may subsequently overestimate more than usual.

Exceptions

ArgumentNullException

item is null.

ArgumentOutOfRangeException

count ≤ 0.

OverflowException

A probed counter or TotalCount would exceed MaxValue.

Clear()

Removes all counts from the sketch by zeroing every counter and resetting TotalCount.

public void Clear()

EstimateCount(T)

Estimates how many times an element has been added to the sketch.

public long EstimateCount(T item)

Parameters

item T

The element to estimate. Must not be null.

Returns

long

The minimum counter value across the element's row probes. The estimate is never less than the element's true count; with probability at least 1 − Delta it is at most the true count plus Epsilon · TotalCount.

Remarks

An element that was never added can still report a positive estimate when its counters collide with added elements; the estimate is zero only when at least one of its counters was never touched.

Exceptions

ArgumentNullException

item is null.

Export(Span<byte>)

Writes the sketch state to destination, which must be at least GetExportByteCount() bytes long.

public void Export(Span<byte> destination)

Parameters

destination Span<byte>

The buffer that receives the exported state.

Exceptions

ArgumentException

destination is shorter than GetExportByteCount() bytes.

GetExportByteCount()

Returns the number of bytes required to export the sketch state via TryExport(Span<byte>, out int) or Export(Span<byte>).

public int GetExportByteCount()

Returns

int

The exact export size in bytes for this sketch's configuration.

Import(ReadOnlySpan<byte>, IEqualityComparer<T>?)

Creates a CountMinSketch<T> from state previously produced by TryExport(Span<byte>, out int) or Export(Span<byte>).

public static CountMinSketch<T> Import(ReadOnlySpan<byte> source, IEqualityComparer<T>? comparer = null)

Parameters

source ReadOnlySpan<byte>

The exported sketch state.

comparer IEqualityComparer<T>

The equality comparer to associate with the imported sketch. Must be the comparer (or an equal comparer) the exporting sketch used, or estimates are undefined. If null, the default equality comparer for T is used.

Returns

CountMinSketch<T>

A new sketch whose counter state matches the exported sketch.

Remarks

The comparer is not part of the exported state; the caller must re-supply it. For element types with process-randomized hash codes (notably string under the default comparer), an export is only meaningful within the process that produced it.

Exceptions

ArgumentException

source is truncated, carries an unsupported format version, or does not describe a valid sketch.

MergeWith(CountMinSketch<T>)

Merges another compatible sketch into this one by adding its counters cell-wise, so that this sketch subsequently estimates the combined stream of both sources.

public void MergeWith(CountMinSketch<T> other)

Parameters

other CountMinSketch<T>

The sketch to merge into this one. Must not be null.

Remarks

Compatibility requires identical Width and Depth and the same or an equal comparer instance - in practice, sketches constructed with the same parameters. The other sketch is not modified, and TotalCount becomes the sum of both totals. Merging a sketch with itself doubles every count.

Cell additions are checked; when an OverflowException is thrown mid-merge, cells merged before the failing one retain the added counts and the sketch may subsequently overestimate more than usual.

Comparer identity is decided by Equals(object) (after a reference check). Two distinct instances of a custom comparer type that does not override Equals(object) compare unequal even when behaviourally identical, and the merge is rejected. Share a single comparer instance between sketches that will be merged, or override Equals (and GetHashCode) on the comparer type.

Exceptions

ArgumentNullException

other is null.

ArgumentException

other is incompatible: its Width, Depth, or comparer differs from this sketch's.

OverflowException

A cell-wise sum or the combined TotalCount would exceed MaxValue.

TryExport(Span<byte>, out int)

Attempts to write the sketch state to destination.

public bool TryExport(Span<byte> destination, out int bytesWritten)

Parameters

destination Span<byte>

The buffer that receives the exported state.

bytesWritten int

When the method returns true, the number of bytes written (always GetExportByteCount()); otherwise 0.

Returns

bool

true when destination is large enough and the state was written; otherwise false.

Applies to

ProductVersions
.NET8, 10