countmin

README

CountMin

CountMin sketching algorithm.

Install

Install package

go get -u github.com/mtchavez/countmin

Usage

package main

import (
	"fmt"

	"github.com/mtchavez/countmin"
)

func main() {
	cm := countmin.New(10, 100000000)
	for _, i := range []int64{1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1} {
		cm.Add([]byte(fmt.Sprintf("%d", i)), int64(i))
	}
	fmt.Printf("Estimate of %d is %d\n", 1, cm.Count([]byte("1")))
	fmt.Printf("Estimate of %d is %d\n", 3, cm.Count([]byte("3")))
	fmt.Printf("Estimate of %d is %d\n", 9, cm.Count([]byte("9")))
	fmt.Println("Size: ", cm.Size())
	fmt.Println("Err: ", cm.RelativeError())
	fmt.Println("Confidence: ", cm.Confidence())
}

Tests

Run using go test ./... --cover

Run benchmarks go test --bench=.*

TODO

• Serialize/Deserialize
• TCP / HTTP server wrappers

Documentation

Index

• Constants
• type CountMin
  • func Merge(cm1, cm2 *CountMin) (*CountMin, error)
  • func New(depth, width int) *CountMin
  • func NewWithEpsCount(confidence, eps float64) *CountMin
  • func (cm *CountMin) Add(item []byte, count int64)
  • func (cm *CountMin) Confidence() float64
  • func (cm *CountMin) Count(item []byte) int64
  • func (cm *CountMin) RelativeError() float64
  • func (cm *CountMin) Size() int64

Examples

• CountMin.Add

Constants

const MAXINT64 = 1<<63 - 1

Max int 64 size

Types

type CountMin

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

CountMin holds count table and hashes for calculating frequencies from a given input (usually a stream of data)

func Merge

func Merge(cm1, cm2 *CountMin) (*CountMin, error)

Merge two CountMin tables and return a new table of their union

func New

func New(depth, width int) *CountMin

New CountMin given a depth and width of the frequency table to use. Returns the newly created CountMin

func NewWithEpsCount

func NewWithEpsCount(confidence, eps float64) *CountMin

NewWithEpsCount initializes a CountMin given a confidence to ensure between 0 < 1.0 which effects number of hashes used and an epsilon between 0 and 1 with a smaller value for higher precision as it affects the width of the table

func (*CountMin) Add

func (cm *CountMin) Add(item []byte, count int64)

Add inserts an item in bytes and a count associated which will also increment size of CountMin

Example

cm := New(10, 100000000)
for _, i := range []int64{1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1} {
	cm.Add([]byte(fmt.Sprintf("%d", i)), int64(i))
}
fmt.Printf("Estimate of %d is %d\n", 1, cm.Count([]byte("1")))
fmt.Printf("Estimate of %d is %d\n", 3, cm.Count([]byte("3")))
fmt.Printf("Estimate of %d is %d\n", 9, cm.Count([]byte("9")))
fmt.Println("Size: ", cm.Size())
fmt.Println("Err: ", cm.RelativeError())
fmt.Println("Confidence: ", cm.Confidence())

Output:

Estimate of 1 is 3
Estimate of 3 is 6
Estimate of 9 is 18
Size:  91
Err:  2e-08
Confidence:  0.9990234375

func (*CountMin) Confidence

func (cm *CountMin) Confidence() float64

Confidence returns confidence of CountMin

func (*CountMin) Count

func (cm *CountMin) Count(item []byte) int64

Count gets an associated total count for an item in the CountMin

func (*CountMin) RelativeError

func (cm *CountMin) RelativeError() float64

RelativeError returns epsilon of CountMin

func (*CountMin) Size

func (cm *CountMin) Size() int64

Size returns total size of CountMin