Skip to content
HyperLogLog++ for Go
Go
Branch: master
Clone or download
timkaye11 Merge pull request #12 from lytics/copy_fix
check if sparselist is nil in copy
Latest commit 70adc91 Apr 10, 2018
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore
LICENSE Fill in blanks in LICENSE Aug 20, 2014
README.md Justify errata corrections based on Stefan's email Aug 27, 2014
bias_tables.go hyperloglogplusplus for go Aug 20, 2014
bitmanip.go Remove some assertions since everything seems to work Aug 20, 2014
bitmanip_test.go hyperloglogplusplus for go Aug 20, 2014
deviations.md
doc.go Freshen docs, add example Aug 20, 2014
example_test.go Documentation tweaks Aug 25, 2014
hll.go add Copy to hll Apr 2, 2018
hll.pb.go
hll.proto protobuf matches struct name Aug 21, 2015
hll_test.go add Copy to hll Apr 2, 2018
marshal_test.go add gob encoder/decoder Sep 23, 2015
normal.go
normal_test.go hyperloglogplusplus for go Aug 20, 2014
sparse.go check if sparselist is nil in copy Apr 6, 2018
sparse_test.go
sparseutil.go Update docs, GetIndex errata are now in appendix Aug 28, 2014
sparseutil_test.go JSON marshalling for save/restore of Hll in progress. Fixes #5 Aug 28, 2014

README.md

HyperLogLog++ for Go

This is a Go implementation of the HyperLogLog++ algorithm from "HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm" by Heule, Nunkesser and Hall of Google. This is a cardinality estimation algorithm: given a stream of input elements, it will estimate the number of unique items in the stream. The estimation error can be controlled by choosing how much memory to use. HyperLogLog++ improves on the basic HyperLogLog algorithm by using less space, improving accuracy, and correcting bias.

This code is a translation of the pseudocode contained in Figures 6 and 7 of the Google paper. Not all algorithms are provided in the paper, but we've tried our best to be true to the authors' intent when writing the omitted algorithms. We're not trying to be creative, we're just implementing the algorithm described in the paper as directly as possible. Our deviations are described here.

The HyperLogLog++ paper is available here

Instructions

See the docs.

You can’t perform that action at this time.