hll

Documentation

Overview

Package hll contains a HyperLogLog++ with a LogLog-Beta bias correction implementation that is adapted (mostly copied) from an implementation provided by Clark DuVall github.com/clarkduvall/hyperloglog.

The differences are that the implementation in this package:

• uses an AMD64 optimised xxhash algorithm instead of murmur;
• uses some AMD64 optimisations for things like clz;
• works with []byte rather than a Hash64 interface, to reduce allocations;
• implements encoding.BinaryMarshaler and encoding.BinaryUnmarshaler

Based on some rough benchmarking, this implementation of HyperLogLog++ is around twice as fast as the github.com/clarkduvall/hyperloglog implementation.

Index

• Constants
• type Plus
  • func MustNewPlus(p uint8) *Plus
  • func NewDefaultPlus() *Plus
  • func NewPlus(p uint8) (*Plus, error)
  • func (h *Plus) Add(v []byte)
  • func (h *Plus) Clone() *Plus
  • func (h *Plus) Count() uint64
  • func (h *Plus) MarshalBinary() (data []byte, err error)
  • func (h *Plus) Merge(s estimator.Sketch) error
  • func (h *Plus) UnmarshalBinary(data []byte) error

Constants

const DefaultPrecision = 16

DefaultPrecision is the default precision.

Types

type Plus

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

Plus implements the Hyperloglog++ algorithm, described in the following paper: http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf

The HyperLogLog++ algorithm provides cardinality estimations.

func MustNewPlus

func MustNewPlus(p uint8) *Plus

MustNewPlus returns a new Plus with precision p. Panic on error.

func NewDefaultPlus

func NewDefaultPlus() *Plus

NewDefaultPlus creates a new Plus with the default precision.

func NewPlus

func NewPlus(p uint8) (*Plus, error)

NewPlus returns a new Plus with precision p. p must be between 4 and 18.

func (*Plus) Add

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

Add adds a new value to the HLL.

func (*Plus) Clone

func (h *Plus) Clone() *Plus

Clone returns a deep copy of h.

func (*Plus) Count

func (h *Plus) Count() uint64

Count returns a cardinality estimate.

func (*Plus) MarshalBinary

func (h *Plus) MarshalBinary() (data []byte, err error)

MarshalBinary implements the encoding.BinaryMarshaler interface.

func (*Plus) Merge

func (h *Plus) Merge(s estimator.Sketch) error

Merge takes another HyperLogLogPlus and combines it with HyperLogLogPlus h. If HyperLogLogPlus h is using the sparse representation, it will be converted to the normal representation.

func (*Plus) UnmarshalBinary

func (h *Plus) UnmarshalBinary(data []byte) error

UnmarshalBinary implements the encoding.BinaryUnmarshaler interface.