countmin

Documentation

Index

• Constants
• type Sketch
  • func New(nrows, ncols int) (*Sketch, error)
  • func NewFromCounts(rows [][]uint32) (sketch *Sketch, err error)
  • func NewFromProb(ε, δ float64) (sketch *Sketch, err error)
  • func (sketch *Sketch) Add(i, c uint32)
  • func (sketch *Sketch) Add1(i uint32)
  • func (sketch *Sketch) AddCU(i, c uint32)
  • func (sketch *Sketch) Copy() *Sketch
  • func (sketch *Sketch) Counts() (rows [][]uint32)
  • func (sketch *Sketch) Get(i uint32) (count uint32)
  • func (sketch *Sketch) NCols() int
  • func (sketch *Sketch) NRows() int
  • func (sketch *Sketch) Sum(other *Sketch) error

Constants

const MaxRows = len(π)

Types

type Sketch

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

Count-min sketch: approximate frequency table, indexed by hash values.

The user is responsible for supplying hash values of observations. Multiple hash functions are simulated by XOR'ing the given hash values with built-in seeds (the binary expansion of π).

func New

func New(nrows, ncols int) (*Sketch, error)

Make a new count-min sketch with the given number of rows and columns.

Returns an error if nrows<1, ncols<1, or nrows exceeds MaxRows.

func NewFromCounts

func NewFromCounts(rows [][]uint32) (sketch *Sketch, err error)

Make a count-min sketch with exactly the given rows. The contents of rows is copied into the sketch.

Errors if the rows are not all of the same length, if any dimension is zero, or any element is negative.

func NewFromProb

func NewFromProb(ε, δ float64) (sketch *Sketch, err error)

Make a count-min sketch that answers point queries within a factor ε off from the true count with probability 1−δ.

func (*Sketch) Add

func (sketch *Sketch) Add(i, c uint32)

Add c observations of type i.

func (*Sketch) Add1

func (sketch *Sketch) Add1(i uint32)

Add one observation of type i.

func (*Sketch) AddCU

func (sketch *Sketch) AddCU(i, c uint32)

Add c observations of type i with conservative updating (Goyal, Daumé and Cormode, Sketch algorithms for estimating point queries in NLP, Proc. EMNLP-CoNLL, 2012).

func (*Sketch) Copy

func (sketch *Sketch) Copy() *Sketch

Returns a copy of the sketch.

func (*Sketch) Counts

func (sketch *Sketch) Counts() (rows [][]uint32)

Returns a copy of the counts in the sketch.

func (*Sketch) Get

func (sketch *Sketch) Get(i uint32) (count uint32)

Point query for observations of type i. Returns an approximate count.

func (*Sketch) NCols

func (sketch *Sketch) NCols() int

func (*Sketch) NRows

func (sketch *Sketch) NRows() int

func (*Sketch) Sum

func (sketch *Sketch) Sum(other *Sketch) error

Add counts of other into sketch.

Returns an error iff the two sketches are not of the same shape.