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