I've come across this paper by Otmar Ertl in Github. If I understand it correctly, he points out that when you use p + q bit hashes, you put integers at most of value q into 2^p registers. Instead, he stores a q long vector and keeps counts in them so that the counts sum to 2^p.

Was this result known previously? Wikipedia does not mention this alternative for the HyperLogLog data structure. It compresses the data structure enormously.

  • $\begingroup$ Upon further thought, it seems the single sketch is compressible but not composable anymore with other sketches. So this new data structure would be useful only on a narrow circumstance where you want to compute numerous estimates for the same sketch using different algorithms. $\endgroup$ – andrescorrada Mar 14 '18 at 18:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.