README
¶
HyperLogLog - an algorithm for approximating the number of distinct elements
An improved version of HyperLogLog for the count-distinct problem, approximating the number of distinct elements in a multiset. This implementation offers enhanced performance, flexibility, and simplicity while maintaining accuracy.
Note on Implementation History
The initial version of this work (tagged as v0.1.0) was based on "Better with fewer bits: Improving the performance of cardinality estimation of large data streams - Qingjun Xiao, You Zhou, Shigang Chen". However, the current implementation has evolved significantly from this original basis, notably moving away from the tailcut method.
Current Implementation
The current implementation is based on the LogLog-Beta algorithm, as described in:
"LogLog-Beta and More: A New Algorithm for Cardinality Estimation Based on LogLog Counting" by Jason Qin, Denys Kim, and Yumei Tung (2016).
Key features of the current implementation:
- Metro hash used instead of xxhash
- Sparse representation for lower cardinalities (like HyperLogLog++)
- LogLog-Beta for dynamic bias correction across all cardinalities
- 8-bit registers for convenience and simplified implementation
- Order-independent insertions and merging for consistent results regardless of data input order
- Removal of tailcut method for a more straightforward approach
- Flexible precision allowing for 2^4 to 2^18 registers
This implementation is now more straightforward, efficient, and flexible, while remaining backwards compatible with previous versions. It provides a balance between precision, memory usage, speed, and ease of use.
Precision and Memory Usage
This implementation allows for creating HyperLogLog sketches with arbitrary precision between 2^4 and 2^18 registers. The memory usage scales with the number of registers:
- Minimum (2^4 registers): 16 bytes
- Default (2^14 registers): 16 KB
- Maximum (2^18 registers): 256 KB
Users can choose the precision that best fits their use case, balancing memory usage against estimation accuracy.
Note
A big thank you to Prof. Shigang Chen and his team at the University of Florida who are actively conducting research around "Big Network Data".
Contributing
Kindly check our contributing guide on how to propose bugfixes and improvements, and submit pull requests to the project.
Run the same checks used by CI before opening a pull request:
make ci
Individual targets are available for formatting (make fmt), linting
(make lint), tests (make test), race-enabled tests (make test-race), and
coverage (make coverage).
Version tags matching v*.*.* are validated by the release workflow before it
publishes a GitHub Release with generated release notes. Tags with a pre-release
suffix, such as v1.0.0-rc.1, publish as pre-releases.
License
© Axiom, Inc., 2026
Distributed under the MIT License (The MIT License).
See LICENSE for more information.
Documentation
¶
Overview ¶
Package hyperloglog implements the HyperLogLog cardinality estimator with sparse and dense representations.
Example ¶
Example demonstrates basic usage.
sketch := New()
sketch.Insert([]byte("alice"))
sketch.Insert([]byte("bob"))
sketch.Insert([]byte("charlie"))
sketch.Insert([]byte("alice")) // Duplicate
fmt.Printf("Estimated unique elements: %d\n", sketch.Estimate())
Output: Estimated unique elements: 3
Example (InsertHash) ¶
Example_insertHash shows using InsertHash when you already have hash values.
sketch := New()
// InsertHash requires values from a high-quality hash function with a
// uniform distribution across all 64 bits. Do not pass sequential IDs
// directly.
sketch.InsertHash(0x1234567890abcdef)
sketch.InsertHash(0xfedcba0987654321)
sketch.InsertHash(0x1111111111111111)
fmt.Printf("Estimated unique elements: %d\n", sketch.Estimate())
Output: Estimated unique elements: 3
Example (Merge) ¶
Example_merge shows merging sketches for distributed counting.
sketch1 := New14()
sketch2 := New14()
for i := range 500 {
buf := fmt.Appendf(nil, "item-%d", i)
sketch1.Insert(buf)
}
for i := range 500 {
buf := fmt.Appendf(nil, "item-%d", i+250)
sketch2.Insert(buf)
}
fmt.Printf("Sketch 1 estimate: %d\n", sketch1.Estimate())
fmt.Printf("Sketch 2 estimate: %d\n", sketch2.Estimate())
if err := sketch1.Merge(sketch2); err != nil {
log.Fatal(err)
}
fmt.Printf("Merged estimate: %d\n", sketch1.Estimate())
Output: Sketch 1 estimate: 500 Sketch 2 estimate: 500 Merged estimate: 750
Example (Precision) ¶
Example_precision shows different precision levels and their trade-offs.
sketch14 := New14() // 16 KB
sketch16 := New16() // 64 KB
for i := range 100 {
buf := fmt.Appendf(nil, "element-%d", i)
sketch14.Insert(buf)
sketch16.Insert(buf)
}
fmt.Printf("Precision 14: %d unique elements\n", sketch14.Estimate())
fmt.Printf("Precision 16: %d unique elements\n", sketch16.Estimate())
Output: Precision 14: 100 unique elements Precision 16: 100 unique elements
Example (Serialization) ¶
Example_serialization demonstrates binary marshaling and error handling.
original := New14()
for i := range 100 {
buf := fmt.Appendf(nil, "user-%d", i)
original.Insert(buf)
}
data, err := original.MarshalBinary()
if err != nil {
log.Fatal(err)
}
restored := New14()
if err := restored.UnmarshalBinary(data); err != nil {
log.Fatal(err)
}
fmt.Printf("Original estimate: %d\n", original.Estimate())
fmt.Printf("Restored estimate: %d\n", restored.Estimate())
fmt.Println("Serialization successful")
Output: Original estimate: 100 Restored estimate: 100 Serialization successful
Index ¶
- Variables
- type Sketch
- func (sk *Sketch) AppendBinary(data []byte) ([]byte, error)
- func (sk *Sketch) Clone() *Sketch
- func (sk *Sketch) Estimate() uint64
- func (sk *Sketch) Insert(e []byte)
- func (sk *Sketch) InsertHash(x uint64)
- func (sk *Sketch) MarshalBinary() (data []byte, err error)
- func (sk *Sketch) Merge(other *Sketch) error
- func (sk *Sketch) Reset()
- func (sk *Sketch) UnmarshalBinary(data []byte) error
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrorInvalidData = errors.New("invalid binary data")
ErrorInvalidData is returned by UnmarshalBinary when the binary is long enough but describes a state that cannot be decoded.
var ErrorInvalidPrecision = errors.New("p has to be >= 4 and <= 18")
ErrorInvalidPrecision is returned unwrapped by NewSketch, and wrapped by UnmarshalBinary, MarshalBinary and AppendBinary, when the precision is outside the supported range.
var ErrorInvalidVersion = errors.New("unknown serialization version")
ErrorInvalidVersion is returned by UnmarshalBinary when the version byte is neither 1 nor 2.
var ErrorPrecisionMismatch = errors.New("precisions must be equal")
ErrorPrecisionMismatch is wrapped by Merge when the sketches have different precisions.
var ErrorTooShort = errors.New("too short binary")
ErrorTooShort is returned, wrapped, when a buffer ends before the format requires. UnmarshalBinary used to return it unwrapped, so err == ErrorTooShort is now always false and callers have to use errors.Is.
Functions ¶
This section is empty.
Types ¶
type Sketch ¶
type Sketch struct {
// contains filtered or unexported fields
}
Sketch is a HyperLogLog estimator. Do not copy one after first use; use Clone. Its zero value is empty and initializes on insertion or merge: a zero value first used with Insert or InsertHash takes New's configuration (precision 14, sparse), while a zero value first used with Merge adopts the other sketch's precision and representation.
func New14 ¶
func New14() *Sketch
New14 returns a HyperLogLog Sketch with 2^14 registers (precision 14)
func New16 ¶
func New16() *Sketch
New16 returns a HyperLogLog Sketch with 2^16 registers (precision 16)
func New16NoSparse ¶
func New16NoSparse() *Sketch
New16NoSparse returns a HyperLogLog Sketch with 2^16 registers (precision 16) that will not use a sparse representation
func NewNoSparse ¶
func NewNoSparse() *Sketch
NewNoSparse returns a HyperLogLog Sketch with 2^14 registers (precision 14) that will not use a sparse representation
func NewSketch ¶ added in v0.2.0
NewSketch returns a HyperLogLog Sketch with 2^precision registers. The precision has to be >= 4 and <= 18, otherwise ErrorInvalidPrecision is returned. When sparse is true the Sketch starts out in the sparse representation.
func (*Sketch) AppendBinary ¶ added in v0.2.3
AppendBinary implements the encoding.BinaryAppender interface.
An uninitialized (zero value) Sketch has no encoding: its precision is 0, so AppendBinary returns an error wrapping ErrorInvalidPrecision and leaves the caller's buffer unmodified.
UnmarshalBinary requires the encoding to be the entire buffer it is handed and rejects trailing bytes with ErrorInvalidData. A caller appending a Sketch into a larger buffer must frame the record itself; the number of bytes appended is len(result) - len(data).
The encoding is not canonical: two sketches holding the same values may encode to different bytes, depending on insertion order and on whether Estimate has compacted the sparse representation. An encoding must not be hashed, deduplicated, or compared for equality to decide whether two sketches hold the same values.
func (*Sketch) InsertHash ¶
InsertHash adds a uniformly distributed 64-bit hash to sk.
func (*Sketch) MarshalBinary ¶
MarshalBinary implements the encoding.BinaryMarshaler interface.
An uninitialized (zero value) Sketch has no encoding: its precision is 0, so MarshalBinary returns an error wrapping ErrorInvalidPrecision.
When the result will be appended to another buffer, consider using AppendBinary to avoid additional allocations and copying.
func (*Sketch) Reset ¶ added in v0.3.0
func (sk *Sketch) Reset()
Reset clears the sketch while preserving its current representation and allocated backing storage.
func (*Sketch) UnmarshalBinary ¶
UnmarshalBinary implements the encoding.BinaryUnmarshaler interface.
The binary format starts with a 4 byte header:
byte 0: version. 2 is written; 1 and 2 are accepted, anything else
returns ErrorInvalidVersion.
byte 1: precision p, which must be in [4, 18], otherwise
ErrorInvalidPrecision is returned.
byte 2: b, the register bias of the version 1 dense payload. It is
ignored for sparse payloads of either version. Version 2 writes
0 and requires 0.
byte 3: 1 if the payload is sparse, 0 if it is dense.
The sparse payload is identical for version 1 and 2: a uint32 big endian count N of tmp set keys, followed by N uint32 big endian keys, followed by the compressed list: a uint32 big endian count, a uint32 big endian last value, a uint32 big endian size sz, and sz bytes of a delta varint stream whose final byte must have its high bit clear. The tmp set keys may appear in any order.
Version 2 pins the hash function to MetroHash64 with seed 1337 and the sparse precision pp to 25. Sparse keys and dense registers are only meaningful under those two constants, so changing either requires a new version byte.
The version 2 dense payload is a uint32 big endian register count, which must equal m = 1<<p, followed by m register bytes. In the version 1 dense payload bytes 4:8 are ignored and bytes 8: hold m/2 bytes of two 4 bit registers each, both biased by b.
Byte 2 must be 0 when the version is 2, and byte 3 must be 0 or 1; any other value returns ErrorInvalidData. The compressed list's count must equal the number of varints in its stream and must be less than 2^25, and its last value must equal the sum of the deltas, otherwise ErrorInvalidData is returned. Each delta varint must be at most 5 bytes long, minimally encoded, and must fit in 32 bits. The running sum of the deltas must strictly increase after the first delta and must not wrap; a first delta of 0 is legal. A violation of either rule returns ErrorInvalidData. Every decoded sparse key and every dense register must decode to a value no greater than 64-p+1, otherwise ErrorInvalidData is returned.
The payload must end exactly where its declared lengths say it does: bytes following the sparse compressed list, the version 2 registers, or the version 1 packed registers return ErrorInvalidData.
Version, precision and every length prefix are validated before the receiver is mutated, so the receiver is never left with registers or a sparse list shorter than the layout implies. If an error is returned sk is left unchanged. Every error returned by UnmarshalBinary wraps one of the exported sentinels above and has to be matched with errors.Is rather than with ==.
Source Files
Directories