hll

Documentation

Overview

Package hll provides an implementation of the HyperLogLog algorithm.

A HyperLogLog counter can approximate the cardinality of a set with high accuracy and little memory.

Accuracy

The counter is built to be accurate up to +-1% for any cardinality starting from 0, with a high probability. This is verified in the tests.

Performance

An HLL counter uses 65kb memory. Adding an element of size up to 100 bytes takes an order of 100ns. Calculating the approximate count takes an order of 4ms.

Citation

Flajolet, Philippe; Fusy, Éric; Gandouet, Olivier; Meunier, Frédéric (2007). "Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm". Discrete Mathematics and Theoretical Computer Science Proceedings.

Index

• type HLL
  • func New() *HLL
  • func NewSeed(seed uint32) *HLL
  • func (h *HLL) Add(v []byte)
  • func (h *HLL) AddHLL(other *HLL)
  • func (h *HLL) ApproxCount() int
  • func (h *HLL) MarshalJSON() ([]byte, error)
  • func (h *HLL) UnmarshalJSON(b []byte) error

Types

type HLL

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

An HLL is a HyperLogLog counter for arbitrary values.

func New

func New() *HLL

New creates a new HyperLogLog counter with a random hash seed.

func NewSeed

func NewSeed(seed uint32) *HLL

NewSeed creates a new HyperLogLog counter with the given hash seed.

func (*HLL) Add

func (h *HLL) Add(v []byte)

Add adds v to the counter. Calls hash once.

func (*HLL) AddHLL

func (h *HLL) AddHLL(other *HLL)

AddHLL adds the state of another counter to h. The result is equivalent to adding all the values of other to h.

func (*HLL) ApproxCount

func (h *HLL) ApproxCount() int

ApproxCount returns the current approximate count. Does not alter the state of the counter.

func (*HLL) MarshalJSON

func (h *HLL) MarshalJSON() ([]byte, error)

MarshalJSON implements the json.Marshaler interface.

func (*HLL) UnmarshalJSON

func (h *HLL) UnmarshalJSON(b []byte) error

UnmarshalJSON implements the json.Unmarshaler interface.