<转> 基数估计算法概览

转自淘宝张洋的基数估计算法概览
翻译自Damn Cool Algorithms: Cardinality Estimation.
在淘宝的应用考虑参考 基数估计算法在大数据场景下的应用.

假如你有一个巨大的含有重复数据项数据集,这个数据集过于庞大以至于无法全部放到内存中处理。现在你想知道这个数据集里有多少不同的元素,但是数据集没有排好序,而且对如此大的一个数据集进行排序和计数几乎是不可行的。你要如何估计数据集中有多少不同的数据项?很多应用场景都涉及这个问题,例如设计数据库的查询策略:一个良好的数据库查询策略不但和总的数据量有关,同时也依赖于数据中不同数据项的数量。

我建议在继续阅读本文前你可以稍微是思考一下这个问题,因为接下来我们要谈的算法相当有创意,而且实在是不怎么直观。

阅读全文