ged-lab/khmer — pull request #257 by luizirber (2014-01-14 21:30:17+00:00)
Title: HyperLogLog Counter

# WIP, Don't merge yet

# HyperLogLog Counter

This implements #233. A HyperLogLog counter is a probabilistic counter capable of cardinality estimation (how many unique elements appears in a dataset) with very low memory consumption. In khmer it can be useful to give better guesses for hash size parameters (-x and -N).

## References

- svpcom/hyperloglog@f91ed5db8ca8f4cf7b364f2a54dd89e0a125a699
- http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
- http://research.google.com/pubs/pub40671.html

## TODO

- [ ] add tests
- [ ] implement Google paper suggestion (64 bits hash function, bias correction)
- [ ] ask @mr-c and @camillescott about the right way to implement extensions
- [ ] think more about get_rho function
- [ ] parallel reading and HLL merges for better performance