How does the HyperLogLog algorithm work?

by

The main trick behind this algorithm is that if you, observing a stream of random integers, see an integer which binary representation starts with some known prefix, there is a higher chance that the cardinality of the stream is 2^(size of the prefix).

That is, in a random stream of integers, ~50% of the numbers (in binary) starts with “1”, 25% starts with “01”, 12,5% starts with “001”. This means that if you observe a random stream and see a “001”, there is a higher chance that this stream has a cardinality of 8.

(The prefix “00..1” has no special meaning. It’s there just because it’s easy to find the most significant bit in a binary number in most processors)

Of course, if you observe just one integer, the chance this value is wrong is high. That’s why the algorithm divides the stream in “m” independent substreams and keep the maximum length of a seen “00…1” prefix of each substream. Then, estimates the final value by taking the mean value of each substream.

That’s the main idea of this algorithm. There are some missing details (the correction for low estimate values, for example), but it’s all well written in the paper. Sorry for the terrible english.

More Related Contents:

  1. How to create the most compact mapping n → isprime(n) up to a limit N?
  2. What’s the Hi/Lo algorithm?
  3. How to create the most compact mapping n → isprime(n) up to a limit N?
  4. Computing set intersection in linear time?
  5. C – How to implement Set data structure?
  6. How to store images in your filesystem
  7. Alternatives to Entity-Attribute-Value (EAV)?
  8. What are the differences between B trees and B+ trees?
  9. How to make fibonacci method? [closed]
  10. is there an algorithm to reverse a chosen part of a number? [closed]
  11. Sum a number with divisors to get another number
  12. The most efficient way to implement an integer based power function pow(int, int)
  13. Reverse the ordering of words in a string
  14. Fast ceiling of an integer division in C / C++
  15. What’s the difference between a catalog and a schema in a relational database?
  16. Difference between scaling horizontally and vertically for databases [closed]
  17. Choosing n numbers with fixed sum
  18. Fast way to calculate n! mod m where m is prime?
  19. Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?
  20. Spring Security 3 database authentication with Hibernate
  21. Is it fine to have foreign key as primary key?
  22. Why use a 1-to-1 relationship in database design?
  23. What is the optimal length for an email address in a database?
  24. Non-Relational Database Design [closed]
  25. sine wave that slowly ramps up frequency from f1 to f2 for a given time
  26. There is already an object named in the database
  27. Limit an sqlite Table’s Maximum Number of Rows
  28. List of standard lengths for database fields
  29. Location of highest density on a sphere
  30. Pros/cons of document-based databases vs. relational databases

Leave a Comment