loglogbeta

package module
v0.0.0-...-f19fdfb Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 13, 2017 License: MIT Imports: 5 Imported by: 2

README

LogLog-Beta GoDoc

LogLog-Beta and More: A New Algorithm for Cardinality Estimation Based on LogLog Counting - by Jason Qin, Denys Kim, Yumei Tung

TL;DR: Better than HyperLogLog in approximating the number unique elements in a set

LogLog-Beta

LogLog-Beta is a new algorithm for estimating cardinalities based on LogLog counting. The new algorithm uses only one formula and needs no additional bias corrections for the entire range of cardinalities, therefore, it is more efficient and simpler to implement. The simulations show that the accuracy provided by the new algorithm is as good as or better than the accuracy provided by either of HyperLogLog or HyperLogLog++.

Using LogLog-Beta
// Create LogLogBeta
llb := loglogbeta.NewDefault()

// Add value to LogLogBeta
llb.Add([]byte("hello"))

// Returns cardinality
llb.Cardinality()

Initial Results

From demo

file:  data/words-1
exact: 150
estimate: 157
ratio: 4.458599%

file:  data/words-2
exact: 1308
estimate: 1373
ratio: 4.734159%

file:  data/words-3
exact: 76205
estimate: 78440
ratio: 2.849312%

file:  data/words-4
exact: 235886
estimate: 236587
ratio: 0.296297%

file:  data/words-5
exact: 349900
estimate: 349388
ratio: -0.146542%

file:  data/words-6
exact: 479829
estimate: 481224
ratio: 0.289886%

total
exact: 660131
estimate: 660548
ratio: 0.063129%

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type LogLogBeta

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

LogLogBeta is a sketch for cardinality estimation based on LogLog counting

func New

func New() *LogLogBeta

New returns a LogLogBeta

func (*LogLogBeta) Add

func (llb *LogLogBeta) Add(value []byte)

Add inserts a value into the sketch

func (*LogLogBeta) AddHash

func (llb *LogLogBeta) AddHash(x uint64)

AddHash ...

func (*LogLogBeta) Cardinality

func (llb *LogLogBeta) Cardinality() uint64

Cardinality returns the number of unique elements added to the sketch

func (*LogLogBeta) MarshalBinary

func (llb *LogLogBeta) MarshalBinary() (data []byte, err error)

MarshalBinary implements the encoding.BinaryMarshaler interface.

func (*LogLogBeta) Merge

func (llb *LogLogBeta) Merge(other *LogLogBeta)

Merge takes another LogLogBeta and combines it with llb one, making llb the union of both.

func (*LogLogBeta) UnmarshalBinary

func (llb *LogLogBeta) UnmarshalBinary(data []byte) error

UnmarshalBinary implements the encoding.BinaryUnmarshaler interface.

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL