# Redis new data structure: the HyperLogLog

DevFeed: [Redis new data structure: the HyperLogLog](<https://devfeed.tech/articles/redis-new-data-structure-the-hyperloglog-20666.md>)

Original publisher: [Read original article](<http://antirez.com/news/75>)

Published: 2014-04-01T08:16:35Z

Content type: release

Language: en

Sources: [Antirez](<https://devfeed.tech/sources/antirez.md>)

Topics: [Redis](<https://devfeed.tech/topics/redis.md>), [Data structures](<https://devfeed.tech/topics/data-structures.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [cardinality](<https://devfeed.tech/tags/cardinality.md>), [data-structure](<https://devfeed.tech/tags/data-structure.md>), [memory](<https://devfeed.tech/tags/memory.md>), [redis](<https://devfeed.tech/tags/redis.md>)

## AI overview

The article introduces HyperLogLog as a new Redis data structure for approximating the number of unique elements in a set. It explains that the algorithm uses a small, constant amount of memory and reports that the Redis implementation uses 12 kB per key with a standard error of 0.81%.

## Source excerpt

Generally speaking, I love randomized algorithms, but there is one I love particularly since even after you understand how it works, it still remains magical from a programmer point of view. It accomplishes something that is almost illogical given how little it asks for in terms of time or space. This algorithm is called HyperLogLog, and today it is introduced as a new data structure for Redis. Counting unique things === Usually counting unique things, for example the number of unique IPs that connected today to your web site, or the number of unique searches that your users performed, requires to remember all the unique elements encountered so far, in order to match the next element with the set of already seen elements, and increment a counter only if the new element was never seen before. This requires an amount of memory proportional to the cardinality (number of items) in the set we are counting, which is, often absolutely prohibitive. There is a class of algorithms that use randomization in order to provide an approximation of the number of unique elements in a set using just a constant, and small, amount of memory. The best of such algorithms currently known is called HyperLogLog, and is due to Philippe Flajolet. HyperLogLog is remarkable as it provides a very good approximation of the cardinality of a set even using a very small amount of memory. In the Redis implementation it only uses 12kbytes per key to count with a standard error of 0.81%, and there is no limit to the number of items you can count, unless you approach 2^64 items (which seems quite unlikely). The algorithm is documented in the original paper [1], and its practical implementation and variants were covered in depth by a 2013 paper from Google [2]. [1] http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf [2] http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf How it works? === There are plenty of wonderful resources to learn more about HyperLogLog, s