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

Average error for 1,000,000,000 elements for different values of logSize:

logSize    average error %
4          21
5          12
6          10
7          8.1
8          4.8
9          3.6
10         1.9
11         1.2
12         1.0
13         0.7
14         0.5
15         0.33
16         0.25

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
• type HLL2
  • func New2[T any](logSize int, h func(T) uint64) *HLL2[T]
  • func (h *HLL2[T]) Add(t T)
  • func (h *HLL2[T]) AddHLL(other *HLL2[T])
  • func (h *HLL2[T]) ApproxCount() int

Types

type HLL

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

An HLL is a HyperLogLog counter for arbitrary values.

Deprecated: use HLL2.

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.

type HLL2

type HLL2[T any] struct {
	// contains filtered or unexported fields
}

An HLL2 is a HyperLogLog counter for arbitrary values.

func New2

func New2[T any](logSize int, h func(T) uint64) *HLL2[T]

New2 creates a new HyperLogLog counter. The counter will use 2^logSize bytes. h is the hash function to use for added values.

func (*HLL2[T]) Add

func (h *HLL2[T]) Add(t T)

Add adds v to the counter. Calls hash once.

func (*HLL2[T]) AddHLL

func (h *HLL2[T]) AddHLL(other *HLL2[T])

AddHLL adds the state of another counter to h, assuming they use the same hash function. The result is equivalent to adding all the values of other to h.

func (*HLL2[T]) ApproxCount

func (h *HLL2[T]) ApproxCount() int

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