Counting the number of users who visit a website accurately requires recording visitor IDs and eliminating duplicates. However, using the algorithm "HyperLogLog" published in 2007, it is possible to estimate the number of users on the scale of hundreds of millions with just a few KB of memory. Scientific American, a science magazine, explains the mechanism of HyperLogLog.

The coin-flipping trick that counts the Internet | Scientific American
https://www.scientificamerican.com/article/the-coin-flipping-trick-that-counts-the-internet/

Counting pageviews on a website is simple; you just need to increment a counter by one each time a page is loaded. On the other hand, accurately counting the number of unique users who have viewed a page requires recording all user IDs and checking against previous records every time there is a new access. When aggregating user counts for each article or post on a website or social networking service used by millions of people, it becomes necessary to store an enormous amount of data.


To solve this problem, Philippe Flajolet from INRIA, the French National Institute for Research in Computer Science and Control, published HyperLogLog in 2007.

HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm | Discrete Mathematics & Theoretical Computer Science | Discrete Mathematics & Theoretical Computer Science
https://dmtcs.episciences.org/en/articles/3545

HyperLogLog is an algorithm that reduces memory usage by estimating the number of unique data items using probability, rather than counting them exactly.

For example, imagine a game where you check how many times a coin lands tails in a row until it lands heads. The probability of getting tails once is 1/2, twice is 1/4, three times is 1/8. The probability of getting tails ten times in a row is 1/1024, so if the game is repeated and the longest record is ten tails, you can estimate that approximately 1000 games were played.


Similarly, if you repeat the game one million times, you can expect tails to come up about 20 times in a row, and about 30 times in a row if you repeat it a billion times. In other words, by just recording the maximum number of consecutive tails, you can roughly estimate how many times the game was played.

Instead of using a coin toss, HyperLogLog uses a "hash function." A hash function is a function that converts input data into a seemingly random value, and has the characteristic that the same input data always produces the same value. By converting a user's ID who accessed a website using a hash function into a sequence of 0s and 1s, and checking how many consecutive 0s appear from the beginning, you can estimate the number of users in the same way as checking how many times tails came up consecutively in a coin toss.

For example, if the maximum number of consecutive zeros at the beginning of the hash values from 10 users is 3, we can estimate the number of users as approximately 8, which is 2 raised to the power of 3. Since the hash function generates the same value for the same user, the maximum number of consecutive zeros will not be updated if the user accesses again. This allows us to estimate the number of distinct users without having to store their IDs.


However, if only one user happens to have an extremely long sequence of zeros in their hash value, the estimate could significantly exceed the actual number of users. To address this, HyperLogLog uses the prefix of the hash values to divide users into multiple groups and estimates the number of users independently in each group.

For instance, if we use the first two digits of the hash value, we can divide users into four groups: '00', '01', '10', and '11'. In each group, we record the maximum position of the first '1' in the remaining bits after the prefix. If the hash value is '10001……', the user is assigned to the '10' group, and the position of the first '1' in the remaining '001……' is recorded as '3' for updating the maximum.

HyperLogLog uses the harmonic mean of the estimates from each group and applies a correction factor to calculate the total number of users. The harmonic mean has the property of reducing the influence of extremely large values, so even if some groups happen to have unusually long sequences of zeros, the overall estimate will not be significantly affected.

The following diagram illustrates the estimation of the number of users using HyperLogLog in a simplified manner. Eight users have accessed a total of nine times, and they are divided into four groups based on the first two digits of their hash values. The estimated number of users in each group is 1, 8, 4, and 4, respectively. Taking the harmonic mean of these values, which is approximately 2.46, and multiplying it by the number of groups, which is 4, gives an estimated total number of users of approximately 9.84.


According to the paper by Flajolet et al., the relative standard error of the HyperLogLog estimates is approximately equal to 1.04 divided by the square root of the number of groups. In a configuration with 2048 groups and each record stored using 5 bits, it is possible to estimate the number of distinct data items exceeding one billion with approximately 2% standard error using about 1.3KB of memory. Increasing the number of groups also makes it possible to reduce the standard error to less than 1%.

HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm
https://research.google/pubs/hyperloglog-in-practice-algorithmic-engineering-of-a-state-of-the-art-cardinality-estimation-algorithm/

The applications of HyperLogLog are not limited to web traffic analysis. It is reportedly being used in situations where one wants to know the number of unique elements within a large amount of data, such as detecting abnormal access by bots in the field of cybersecurity and investigating similarities between genomes in the field of biology.