4 ms·

For anyone wondering what HyperLogLog is: HyperLogLog is an algorithm for the count-distinct problem, approximating the number of distinct elements in a multis

by zwarag 6y ago

For anyone wondering what HyperLogLog is: HyperLogLog is an algorithm for the count-distinct problem, approximating the number of distinct elements in a multiset. Calculating the exact cardinality of a multiset requires an amount of memory proportional to the cardinality, which is impractical for very large data sets. Probabilistic cardinality estimators, such as the HyperLogLog algorithm, use significantly less memory than this, at the cost of obtaining only an approximation of the cardinality. The HyperLogLog algorithm is able to estimate cardinalities of > 109 with a typical accuracy (standard error) of 2%, using 1.5 kB of memory. Source: https://en.wikipedia.org/wiki/HyperLogLog https://en.wikipedia.org/wiki/HyperLogLog

wenc 6y ago
Hyperloglog is part of a class of algorithms known as “sketches”, which use precomputed probabilistic data structures to perform fast but approximate computations on very large data sets. Supported computations include count distinct, frequency, sampling, and quantiles and histograms. There’s a project called Apache Datasketches (developed at Yahoo) that implements production versions of these algorithms. They are useful in the implementations of search engines, discussion forum software, etc. that are designed for scale. https://datasketches.apache.org/docs/Background/TheChallenge.html https://datasketches.apache.org/docs/Background/TheChallenge... Another sketch is the well-known Bloom filter, which can quickly test if an element is part of a set without ever returning a false negative (useful for quickly checking a large database for whether a particular username is still available).
skrebbel 6y ago
For anyone wondering what a multiset is: A multiset is a set where each element can be present multiple times. In other words, it's like an array or list but you don't care about the order.

by zwarag 6y ago

wenc 6y ago

Hyperloglog is part of a class of algorithms known as “sketches”, which use precomputed probabilistic data structures to perform fast but approximate computations on very large data sets. Supported computations include count distinct, frequency, sampling, and quantiles and histograms. There’s a project called Apache Datasketches (developed at Yahoo) that implements production versions of these algorithms. They are useful in the implementations of search engines, discussion forum software, etc. that are designed for scale. https://datasketches.apache.org/docs/Background/TheChallenge.html https://datasketches.apache.org/docs/Background/TheChallenge... Another sketch is the well-known Bloom filter, which can quickly test if an element is part of a set without ever returning a false negative (useful for quickly checking a large database for whether a particular username is still available).

skrebbel 6y ago

For anyone wondering what a multiset is: A multiset is a set where each element can be present multiple times. In other words, it's like an array or list but you don't care about the order.