HyperLogLog

本网站旨在探索以下论文

• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm (2007)
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm (2013)

包含以下部分概念

• 探索 HyperLogLog 如何工作的原理
• 探索 HyperLogLog 如何添加数据项
• 探索 HyperLogLog 如何基于近似的计数
• 探索 HyperLogLog 如何支持合并
• 探索 HyperLogLog 的衍生和具体实践

总而言之

HyperLogLog 是基数估计的利器：

• ✅ 很快
• ✅ 占用内存小
• ✅ 可并发计算
• ✅ 满足交换律

但是：

• ⚠️ 无法给出精确统计 - 根据场景结果可能会出现小的 +/- 偏差(标准误差为 0.81%)
• ⚠️ 无法删除已有元素，只能插入

潜在应用场景：

• 估算有多少独立用户/IP访问了同一个网站
• 度量操作数的时间序列数据
• 数据库查询设计
• 探索性分析

致谢

• 原文：https://djhworld.github.io/hyperloglog/
• HyperLogLog 原理讲解：https://www.cnblogs.com/linguanh/p/10460421.html
• HyperLogLog 和 LogLog 比较：http://content.research.neustar.biz/blog/hll.html