为什么Hyperloglog是有效的?现实世界中存在哪些问题？

Question

我知道Hyperloglog是如何工作的，但我想知道它真正适用于哪些实际情况，即使用Hyperloglog是有意义的，为什么？如果你在解决任何实际问题时使用过，请分享。我正在寻找的是，鉴于Hyperloglog的标准错误，它现在真正用于哪些现实世界的应用程序，为什么它能工作？

Answer 1

(“基数估计的应用”，太广泛了？我想简单地将其添加为注释，但它不适合)。

我建议你转向这个主题的大量学术研究；通常学术论文中包含一些“关于该主题的先前研究”以及“该主题已用于的应用”的信息。您可以从遍历以下文章所引用的感兴趣的引用开始：

P. Flageolet等人的

• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm，。

...在过去的二十年中，这个问题受到了极大的关注，在网络和流量监控中发现了越来越多的应用，例如检测蠕虫传播，检测网络攻击(例如，通过拒绝服务)，以及网络上基于链接的垃圾邮件3。例如，网络上的数据流由一系列分组组成，每个分组具有报头，报头包含一对(源-目的地)地址，后面跟着一组特定的数据；不同时间片中不同报头对(多集的基数)的数量是检测攻击和监控流量的重要指标，因为它记录了不同活动流的数量。事实上，蠕虫和病毒通常通过打开大量不同的连接来传播，尽管它们很可能在巨大的流量中不被注意到，但一旦测量到基数，它们的活动就会暴露出来(参见Estan和Varghese在11中的清晰阐述)。基数估计器的其他应用包括对各种海量数据集的数据挖掘-自然语言文本4、5、生物数据17、18、超大型结构化数据库或互联网图形，其中22的作者报告了通过概率基数估计器获得的500+因子的计算收益。

Answer 2

在我的工作中，HyperLogLog用于估计在线服务中命中不同代码路径的独立用户或独立设备的数量。例如，每种类型的服务错误会影响多少用户？每项功能有多少用户使用？HyperLogLog允许我们回答许多有趣的问题。