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 using 33-50% less space than other usual HyperLogLog implementations.
This work is based on "Better with fewer bits: Improving the performance of cardinality estimation of large data streams - Qingjun Xiao, You Zhou, Shigang Chen".
Implementation
The core differences between this and other implementations are:
- use metro hash instead of xxhash
- sparse representation for lower cardinalities (like HyperLogLog++)
- loglog-beta for dynamic bias correction medium and high cardinalities.
- 4-bit register instead of 5 (HLL) and 6 (HLL++), but most implementations use 1-byte registers out of convenience
In general it borrows a lot from InfluxData's fork of Clark Duvall's HyperLogLog++ implementation, but uses 50% less space.
Results
A direct comparison with the HyperLogLog++ implementation used by InfluxDB yielded the following results:
| Exact | Axiom (8.2 KB) | Influx (16.39 KB) |
|---|---|---|
| 10 | 10 (0.0% off) | 10 (0.0% off) |
| 50 | 50 (0.0% off) | 50 (0.0% off) |
| 250 | 250 (0.0% off) | 250 (0.0% off) |
| 1250 | 1249 (0.08% off) | 1249 (0.08% off) |
| 6250 | 6250 (0.0% off) | 6250 (0.0% off) |
| 31250 | 31008 (0.7744% off) | 31565 (1.0080% off) |
| 156250 | 156013 (0.1517% off) | 156652 (0.2573% off) |
| 781250 | 782364 (0.1426% off) | 775988 (0.6735% off) |
| 3906250 | 3869332 (0.9451% off) | 3889909 (0.4183% off) |
| 10000000 | 9952682 (0.4732% off) | 9889556 (1.1044% off) |
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 submitting pull requests to the project
License
© Axiom, Inc., 2024
Distributed under MIT License (The MIT License).
See LICENSE for more information.
Documentation
¶
Index ¶
- Variables
- type Sketch
- func (sk *Sketch) Clone() *Sketch
- func (sk *Sketch) Estimate() uint64
- func (sk *Sketch) Insert(e []byte) bool
- func (sk *Sketch) InsertHash(x uint64) bool
- func (sk *Sketch) MarshalBinary() (data []byte, err error)
- func (sk *Sketch) Merge(other *Sketch) error
- func (sk *Sketch) UnmarshalBinary(data []byte) error
Constants ¶
This section is empty.
Variables ¶
var ErrorTooShort = errors.New("too short binary")
ErrorTooShort is an error that UnmarshalBinary try to parse too short binary.
Functions ¶
This section is empty.
Types ¶
type Sketch ¶
type Sketch struct {
// contains filtered or unexported fields
}
Sketch is a HyperLogLog data-structure for the count-distinct problem, approximating the number of distinct elements in a multiset.
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 (*Sketch) InsertHash ¶
InsertHash adds hash x to sketch
func (*Sketch) MarshalBinary ¶
MarshalBinary implements the encoding.BinaryMarshaler interface.
func (*Sketch) Merge ¶
Merge takes another Sketch and combines it with Sketch h. If Sketch h is using the sparse Sketch, it will be converted to the normal Sketch.
func (*Sketch) UnmarshalBinary ¶
UnmarshalBinary implements the encoding.BinaryUnmarshaler interface.
Source Files
Directories