package hll

import "github.com/influxdata/influxdb/pkg/estimator/hll"

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 NewDefaultPlus() *Plus
• func NewPlus(p uint8) (*Plus, error)
• func (h *Plus) Add(v []byte)
• func (h *Plus) Bytes() int
• func (h *Plus) Clone() estimator.Sketch
• 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 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) Bytes ¶

func (h *Plus) Bytes() int

Bytes estimates the memory footprint of this Plus, in bytes.

func (*Plus) Clone ¶

func (h *Plus) Clone() estimator.Sketch

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.

Source Files ¶

compressed.go hll.go