algorithm - 将 HyperLogLog 应用于总体样本

Question

HyperLogLogFlajolet 等人的算法描述了一种估计基数的巧妙方法一组只使用少量内存。然而，它确实考虑到了在计算中考虑原始集合的所有 N 个元素。如果什么我们只能访问原始 N 的一小部分随机样本(比如 10%)？是否有任何关于 HyperLogLog 或类似算法如何实现的研究？适应这种情况？

我知道这本质上是被描述为不同的问题值(value)估计，对此存在大量研究(例如，参见 thispaper 的概述)。然而，我所知道的关于独特值(value)估计的研究使用了一个数字与 HyperLogLog 使用的方法非常不同的临时估计器。因此，我想知道是否有人已经考虑过适配HyperLogLog 到单值估计问题。

Answer 1

However, the research on the distinct value estimation that I'm aware of uses a number of ad-hoc estimators very different from the approach used by HyperLogLog.

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

假设您刚刚没收了 1.000.000 美元的假钞，并且您想知道不同序列号的数量。

对其中的 100,000 个进行采样(使用 HyperLogLog，因为您的古董 Steam 驱动计数机只有 1k 内存)，您计算出 5000 个不同的序列号，每个序列号出现大约 20 次。然后您可以非常确定整个藏匿处将只包含 5000 多个不同的序列号。

现在假设1个序号出现95.001次，4999个序号只出现一次。显然，一些真正的钞票进入了您的藏匿处。现在您可以非常确信藏匿处包含大约 5% 的真实钞票，因此整个藏匿处包含大约 50.000 个不同的序列号

请注意，样本中的频率分布用于推断整个存储区中的分布情况。这实际上被称为 second paper 中的“临时”(您的话)方法之一。你引用(“基于采样的不同值数量估计(..)”):

The idea behind a parametric estimator is to fit a probability distribution to the observed relative frequencies of the different attribute values.

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

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