HyperLogLog
flajolet等人的算法描述了一种估计基数的聪明方法
只使用少量内存的集合。但是，它确实需要
在计算中计算原始集合的所有n个元素。如果…怎么办
我们只能得到一个小的随机样本（比如说，10%）的原始N？
有没有研究过hyperloglog或类似的算法
适应这种情况？
我知道这本质上是一个明显的问题
价值估计，其中有丰富的研究存在（见例如AA>概述）。然而，
我所知的不同值估计的研究使用了一个数
与hyperloglog使用的方法有很大不同。
因此，我想知道是否有人已经考虑过适应
超对数到离散值估计问题。
最佳答案
然而，我知道的关于不同价值估计的研究
使用了一些与该方法非常不同的特别估计器
由hyperloglog使用。
是的，因为他们正在解决一个完全不同的问题。
假设你刚刚没收了一堆100万张假钞，你想知道不同的序列号。
对其中的100.000个进行采样（使用hyperloglog，因为你的老式蒸汽计数机只有1k内存），你可以对5000个不同的序列号进行计数，每个序列号大约发生20次。然后你就可以很确定整个储藏室只会包含5000多个不同的序列号。
现在假设1个序列号出现95.001次，4999个序列号只出现一次。很显然，一些真正的钞票进入了你的储藏室。现在你可以很有信心，这个储藏室里有大约5%的真钞，所以整个储藏室里有大约5万个不同的序列号
请注意，样本中频率的分布用于推断整个存储中的分布。这实际上被称为您引用的second paper中的“特别”（单词）方法之一（“基于采样的不同值数目估计（..）”）：
参数估计器背后的思想是将概率分布拟合到
观察不同属性值的相对频率。
还要注意，hyperloglog和类似方法的结果对样本在其值上的分布完全不敏感。但你的最终估计显然在很大程度上取决于它！
我的建议是：使用您选择的方法（如hyperloglog）来计算样本中不同值的数量，然后使用“基于采样的估计”中的一种方法来估计整个多集中的值的数量，或者利用你对多集分布的先验知识来计算一个估计值（也许你看到了造假者的印刷机，你知道它只能打印一个序列号）