Flajolet等人的HyperLogLog算法描述了一种仅使用少量内存来估计集合基数的巧妙方法 . 但是，它确实考虑了计算中原始集合的所有N个元素 . 如果我们只能获得原始N的一小部分随机样本（比方说，10％）怎么办？有没有关于HyperLogLog或类似算法如何适应这种情况的研究？
我知道这基本上是描述为不同 Value 估计的问题，对此存在大量研究（例如参见this paper） . 然而，我所知道的关于独特 Value 估计的研究使用了许多与HyperLogLog使用的方法截然不同的特别估计 . 因此，我想知道是否有人已经考虑过将HyperLogLog调整为不同的 Value 估计问题 .
2 回答
是的，因为他们正在解决一个非常不同的问题 .
假设你刚刚没收了1000,000美元的伪钞，你想知道不同序列号的数量 .
采样100.000（使用HyperLogLog，因为您的古董蒸汽驱动计数机只有1k内存），您可以计算5000个不同的序列号，每个序列号大约发生20次 . 然后你可以非常肯定整个藏匿处只包含5000多个不同的序列号 .
现在假设1个序列号出现95.001次，4999个序列号只出现一次 . 显然，一些真正的银行纸币进入你的藏匿处 . 现在你可以非常自信地藏匿了大约5％的诚实钞票，因此整个存储包含大约50,000个不同的序列号
请注意，样本中频率的分布用于推断整个存储中的分布情况 . 这实际上被提到为second paper中的一个"ad hoc"（你的话）方法（"Sampling-based estimation of the number of distinct values(..)"）：
另请注意，HyperLogLog和类似方法的结果对样本在其值上的分布完全不敏感 . 但是你的最终估计显然在很大程度上取决于它！
我的建议：使用您选择的方法（如HyperLogLog）来计算样本中不同值的数量，然后使用"Sampling-based estimation"中的一种方法来估算整个多重集中的值的数量，或者使用您之前的知识 . 多重集的分布来计算估计值（也许你看过造假者的印刷机，你知道它只能打印一个序列号）
引文搜索是一件很棒的事情 . 我对这两个问题并不是很熟悉，所以这篇论文可能并不完全是你的意思 . 至少他们肯定会谈论HyperLogLog及其与问题的关系，所以也许它会满足你的好奇心 .
An Optimal Algorithm for the Distinct Elements Problem