probably

README

Probabilistic Data Structures

When you need to have a good idea of something, but don't need and/or can't afford to know exactly the right answer, there are probabilistic data structures.

For more how and why, check out this blog post.

Documentation

Index

• type HyperLogLog
  • func NewHyperLogLog(stdErr float64) *HyperLogLog
  • func (h *HyperLogLog) Add(hash uint32)
  • func (h *HyperLogLog) Count() uint64
  • func (h *HyperLogLog) Merge(from *HyperLogLog)
• type ItemCount
• type Sketch
  • func NewSketch(w, d int) *Sketch
  • func (s *Sketch) Add(h string, count uint32) (val uint32)
  • func (s *Sketch) Clone() *Sketch
  • func (s *Sketch) Compress()
  • func (s *Sketch) ConservativeAdd(h string, count uint32) (val uint32)
  • func (s *Sketch) ConservativeIncrement(h string) (val uint32)
  • func (s Sketch) Count(h string) uint32
  • func (s Sketch) CountMeanMin(h string) uint32
  • func (s *Sketch) Del(h string, count uint32) (val uint32)
  • func (s *Sketch) Increment(h string) (val uint32)
  • func (s *Sketch) Merge(from *Sketch)
  • func (s *Sketch) Reset()
  • func (s Sketch) String() string
  • func (s Sketch) Values(h string) []uint32
• type StreamTop
  • func NewStreamTop(w, d, maxItems int) *StreamTop
  • func (s *StreamTop) Add(v string)
  • func (s StreamTop) GetTop() []ItemCount
  • func (s *StreamTop) Merge(from *StreamTop)

Types

type HyperLogLog

type HyperLogLog struct {
	// contains filtered or unexported fields
}

A HyperLogLog cardinality estimator.

See http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf for more information.

func NewHyperLogLog

func NewHyperLogLog(stdErr float64) *HyperLogLog

NewHyperLogLog returns an estimator for counting cardinality to within the given stderr.

Smaller values require more space, but provide more accurate results. For a good time, try 0.001 or so.

func (*HyperLogLog) Add

func (h *HyperLogLog) Add(hash uint32)

Add an item by its hash.

func (*HyperLogLog) Count

func (h *HyperLogLog) Count() uint64

Count returns the current estimate of the number of distinct items seen.

func (*HyperLogLog) Merge

func (h *HyperLogLog) Merge(from *HyperLogLog)

Merge another HyperLogLog into this one.

type ItemCount

type ItemCount struct {
	Key   string
	Count uint32
}

ItemCount represents an item with its count

type Sketch

type Sketch struct {
	// contains filtered or unexported fields
}

Sketch is a count-min sketcher.

func NewSketch

func NewSketch(w, d int) *Sketch

NewSketch returns new count-min sketch with the given width and depth. Sketch dimensions must be positive. A sketch with w=⌈ ℯ/𝜀 ⌉ and d=⌈ln (1/𝛿)⌉ answers queries within a factor of 𝜀 with probability 1-𝛿.

func (*Sketch) Add

func (s *Sketch) Add(h string, count uint32) (val uint32)

Add 'count' occurences of the given input

func (*Sketch) Clone

func (s *Sketch) Clone() *Sketch

Clone returns a copy of this sketch

func (*Sketch) Compress

func (s *Sketch) Compress()

Compress reduces the space used by the sketch. This also reduces the accuracy. This routine panics if the width is not a power of two.

func (*Sketch) ConservativeAdd

func (s *Sketch) ConservativeAdd(h string, count uint32) (val uint32)

ConservativeAdd adds the count (conservatively) for the given input.

func (*Sketch) ConservativeIncrement

func (s *Sketch) ConservativeIncrement(h string) (val uint32)

ConservativeIncrement increments the count (conservatively) for the given input.

func (Sketch) Count

func (s Sketch) Count(h string) uint32

Count returns the estimated count for the given input.

func (Sketch) CountMeanMin

func (s Sketch) CountMeanMin(h string) uint32

CountMeanMin returns estimated count for the given input, using the count-min-mean heuristic. This gives more accurate results than Count() for low-frequency counts at the cost of larger under-estimation error. For tasks sensitive to under-estimation, use the regular Count() and only call ConservativeAdd() and ConservativeIncrement() when constructing your sketch.

func (*Sketch) Del

func (s *Sketch) Del(h string, count uint32) (val uint32)

Del removes 'count' occurences of the given input

func (*Sketch) Increment

func (s *Sketch) Increment(h string) (val uint32)

Increment the count for the given input.

func (*Sketch) Merge

func (s *Sketch) Merge(from *Sketch)

Merge the given sketch into this one. The sketches must have the same dimensions.

func (*Sketch) Reset

func (s *Sketch) Reset()

Reset clears all the values from the sketch.

func (Sketch) String

func (s Sketch) String() string

func (Sketch) Values

func (s Sketch) Values(h string) []uint32

Values returns the all the estimates for a given string

type StreamTop

type StreamTop struct {
	// contains filtered or unexported fields
}

StreamTop tracks the top-n items in a stream.

func NewStreamTop

func NewStreamTop(w, d, maxItems int) *StreamTop

NewStreamTop returns an estimator for the 'maxItems' in the stream. It uses a count-min sketch, which is created with width w and depth d.

func (*StreamTop) Add

func (s *StreamTop) Add(v string)

Add an item to the stream counter.

func (StreamTop) GetTop

func (s StreamTop) GetTop() []ItemCount

GetTop returns the top items from the stream

func (*StreamTop) Merge

func (s *StreamTop) Merge(from *StreamTop)

Merge the given stream into this one.