Documentation
¶
Overview ¶
Package cms provides a Count-Min Sketch for frequency estimation.
A Count-Min Sketch estimates the frequency of elements in a data stream using bounded overestimation. It answers "how many times has this element been seen?" with an estimate that is always >= the true count (for positive-only additions) and bounded by epsilon * totalCount with probability >= 1 - delta.
This implementation uses multiple independent hash functions derived from FNV-1a with per-row seeds mixed via a splitmix64 finalizer.
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ( // ErrInvalidEpsilon is returned when epsilon is not positive. ErrInvalidEpsilon = errors.New("cms: epsilon must be positive") // ErrInvalidDelta is returned when delta is not in the open interval (0, 1). ErrInvalidDelta = errors.New("cms: delta must be in the open interval (0, 1)") )
Functions ¶
This section is empty.
Types ¶
type Sketch ¶
type Sketch struct {
// contains filtered or unexported fields
}
Sketch is a thread-safe Count-Min Sketch for frequency estimation.
func New ¶
New creates a Count-Min Sketch with automatic sizing from the desired error bounds. Width = ceil(e / epsilon), depth = ceil(ln(1 / delta)). Returns an error if epsilon <= 0 or delta is not in (0, 1).
func (*Sketch) Count ¶
Count returns the estimated frequency of key. For positive-only additions, the estimate is always >= the true count.
func (*Sketch) Reset ¶
func (s *Sketch) Reset()
Reset clears all counters and the total count without reallocation.
func (*Sketch) TotalCount ¶
TotalCount returns the sum of all counts added to the sketch.
Source Files