README
¶
Count-Min-Log
TL;DR: Count-Min-Log Sketch for improved Average Relative Error on low frequency events
Count-Min Sketch is a widely adopted algorithm for approximate event counting in large scale processing. However, the original version of the Count-Min-Sketch (CMS) suffers of some deficiences, especially if one is interested in the low-frequency items, such as in text- mining related tasks. Several variants of CMS have been proposed to compensate for the high relative error for low-frequency events, but the proposed solutions tend to correct the errors instead of preventing them. In this paper, we propose the Count-Min-Log sketch, which uses logarithm-based, approximate counters instead of linear counters to improve the average relative error of CMS at constant memory footprint.
Example Usage
8-bit version
import cml
...
sk, err := cml.NewDefaultSketch8()
sk.IncreaseCount([]byte("scott pilgrim"))
...
sk.GetCount("scott pilgrim")
// >> 1
16-bit version
import cml
...
sk, err := cml.NewDefaultSketch16()
sk.IncreaseCount([]byte("scott pilgrim"))
...
sk.GetCount("scott pilgrim")
// >> 1
Documentation
¶
Overview ¶
Package cml implments the Count-Min-Log datastructure.
It is based on Count-Min-Log sketch: Approximately counting with approximate counters - Guillaume Pitel & Geoffroy Fouquier
http://iswag-symposium.org/2015/pdfs/shortpaper1.pdf
TL;DR: Count-Min-Log Sketch for improved Average Relative Error on low frequency events
Count-Min Sketch is a widely adopted algorithm for approximate event counting in large scale processing. However, the original version of the Count-Min-Sketch (CMS) suffers of some deficiences, especially if one is interested in the low-frequency items, such as in text- mining related tasks. Several variants of CMS have been proposed to compensate for the high relative error for low-frequency events, but the proposed solutions tend to correct the errors instead of preventing them. In this paper, we propose the Count-Min-Log sketch, which uses logarithm-based, approximate counters instead of linear counters to improve the average relative error of CMS at constant memory footprint.
Index ¶
- type Sketch
- func NewDefaultSketch() (*Sketch, error)
- func NewForCapacity16(capacity uint64, e float64) (*Sketch, error)
- func NewSketch(w uint, k uint, conservative bool, exp float64, maxSample bool, ...) (*Sketch, error)
- func NewSketchForEpsilonDelta(epsilon, delta float64) (*Sketch, error)
- func Unmarshal16(b []byte) (*Sketch, error)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Sketch ¶
type Sketch struct {
// contains filtered or unexported fields
}
Sketch is a Count-Min-Log sketch 16-bit registers
func NewDefaultSketch ¶
NewDefaultSketch returns a new Count-Min-Log sketch with 16-bit registers and default settings
func NewForCapacity16 ¶
NewForCapacity16 returns a new Count-Min-Log sketch with 16-bit registers optimized for a given max capacity and expected error rate
func NewSketch ¶
func NewSketch(w uint, k uint, conservative bool, exp float64, maxSample bool, progressive bool, nBits uint) (*Sketch, error)
NewSketch returns a new Count-Min-Log sketch with 16-bit registers
func NewSketchForEpsilonDelta ¶
NewSketchForEpsilonDelta ...
func Unmarshal16 ¶
Unmarshal16 returns a Sketch from an serialized byte array
func (*Sketch) IncreaseCount ¶
IncreaseCount increases the count of `s` by one, return true if added and the current count of `s`
func (*Sketch) Probability ¶
Probability returns the error probability of `s`
func (*Sketch) Reset ¶
func (sk *Sketch) Reset()
Reset the Sketch to a fresh state (all counters set to 0)
func (*Sketch) TotalCount ¶
TotalCount returns total count of samples
Source Files