HyperLogLog在人群样本中的应用

Question

弗拉乔莱等人提出的HyperLogLog算法描述了一种聪明的方法，只需少量内存就可以估计集合的基数。但是，它在计算中确实考虑到了原始集合的所有N个元素。如果我们只能获得一个小的随机样本(比如说，10%)的原始N呢？对于HyperLogLog或类似的算法如何适应这种情况，有过研究吗？

我意识到，这本质上是描述为不同价值估计的问题，对此有大量的研究(例如，请参见本论文的概述)。然而，我所知道的关于不同价值估计的研究使用了许多与HyperLogLog所使用的方法截然不同的即席估值器。因此，我想知道是否有人已经考虑过将HyperLogLog应用于不同的值估计问题。

Answer 1

然而，我所知道的关于不同价值估计的研究使用了许多与HyperLogLog所使用的方法截然不同的即席估值器。

是的，因为他们正在解决一个完全不同的问题。

假设你刚刚没收了1.000.000张假钞，你想知道不同序列号的号码。

其中的100.000个样本(使用HyperLogLog，因为你的老式蒸汽驱动计数机只有1k内存)你可以数到5000个不同的序列号，每个序列号大约有20次。然后，您可以非常肯定的是，整个藏匿将只包含一个略多于5000不同的序列号。

现在假设一个序列号出现95.001次，而4999序列号只发生一次。很明显一些真正的钞票进入了你的藏身处。现在，您可以非常自信地相信，藏匿的纸币中大约有5%是诚实的，所以整个藏起来包含大约50.000个不同的序列号。

请注意，样本中频率的分布用于推断整个藏品中的频率分布。这实际上是您所引用的第二篇论文 (“基于抽样估计不同值的数量(.)”中的"ad“方法之一：

参数估计的思想是将概率分布与不同属性值的观测相对频率进行拟合。

还请注意，HyperLogLog和类似方法的结果对样本在其值上的分布完全不敏感。但你的最终估计显然在很大程度上取决于它！

我的建议是:使用您选择的方法(如HyperLogLog)来计算样本中不同值的数量，然后使用“基于抽样的估计”中的一种方法来估计整个多集中的值数，或者使用您的先验知识来计算多集的分布(也许您看到了伪造印刷机，并且知道它只能打印一个序列号)。

Answer 2

引文搜索是一件很棒的事情。我对所提出的两个问题并不十分熟悉，所以这篇论文可能不是你的意思。至少，他们肯定会谈论HyperLogLog及其与问题的关系，所以也许它会满足你的好奇心。

离散元素问题的一种优化算法