# Flajolet, Philippe, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. "Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm." DMTCS Proceedings 1 (2008).
# Heule, Stefan, Marc Nunkesser, and Alexander Hall. "HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm." In Proceedings of the 16th International Conference on Extending Database Technology, pp. 683-692. ACM, 2013.
==统计频率算法==
问题：Frequency Estimation, 估计某个element重复出现次数, 比如, 某个用户对网站访问次数
*Count-Min Sketch 算法
前面要求不需要精确的计数，Count-Min Sketch 就是用来解决此类问题的算法。
这个算法的技巧是：不存储所有的不同的元素，只存储它们Sketch的计数。
*基本的思路
创建一个长度为 x 的数组，用来计数，初始化每个元素的计数值为 0；
对于一个新来的元素，哈希到 0 到 x 之间的一个数，比如哈希值为 i，作为数组的位置索引；
这是，数组对应的位置索引 i 的计数值加 1；
那么，这时要查询某个元素出现的频率，只要简单的返回这个元素哈希望后对应的数组的位置索引的计数值即可。
*如何优化？
使用多个数组，和多个哈希函数，来计算一个元素对应的数组的位置索引；
那么，要查询某个元素的频率时，返回这个元素在不同数组中的计数值中的最小值即可。
改进的算法比原始的算法精确多了，但还是会有冲突，但是冲突少多了。
*算法评价
只会估算偏大，永远不会偏小；
只需要固定大小的内存和计算时间，和需要统计的元素多少无关；
对于低频的元素，估算值相对的错误可能会很大。
这个其实就是bloom过滤器在统计方面的变型。
== 聚类（Clustering） ==