3 ms·
Wikipedia’s list of algorithms and data structures is pretty extensive: https://en.m.wikipedia.org/wiki/List_of_algorithms https://en.m.wikipedia.org/wiki/List
by O__________O 4y ago
Wikipedia’s list of algorithms and data structures is pretty extensive:
https://en.m.wikipedia.org/wiki/List_of_algorithms https://en.m.wikipedia.org/wiki/List_of_algorithms
https://en.m.wikipedia.org/wiki/List_of_data_structures https://en.m.wikipedia.org/wiki/List_of_data_structures
__________________
As for a specific algorithm, this paper covers analysis of HyperLogLog (HLL):
http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
TLDR: 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 > 10^9 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
Recent HN coverage of HyperLogLog:
https://news.ycombinator.com/item?id=32138790 https://news.ycombinator.com/item?id=32138790