HyperLogLogFlajolet等人的算法描述了一种估计基数的巧妙方法只使用少量内存的集合。然而，它确实考虑到了在计算中考虑原始集合的所有N个元素。如果我们只能获得原始N的一小部分随机样本(比如10%)？是否有任何关于HyperLogLog或类似算法的研究适应这种情况？
我知道这本质上是一个被描述为不同的问题价值估计，对此有大量研究(例如，请参阅论文概述)。然而我所知道的关于不同价值估计的研究使用了一个数字与HyperLogLog使用的方法非常不同。因此，我想知道是否有人已经考虑过适应HyperLogLog解决了差异值估计问题。
然而，我所知道的关于不同价值估计的研究of使用了许多与该方法非常不同的ad-hoc估计器HyperLogLog使用。
是的，因为他们正在解决一个完全不同的问题。
假设你刚刚没收了1000万张伪造的美元钞票，你想知道不同序列号的数量。
采样100000个序列号(使用HyperLogLog，因为你的老式蒸汽驱动计数机只有1k内存)，你可以计数5000个不同的序列号，每个序列号大约发生20次。然后你可以非常确定，整个藏匿处只包含5000多个不同的序列号。
现在假设1个序列号出现95.001次，4999个序列号只出现一次。显然，一些真正的钞票进入了你的藏匿处。现在你可以非常确信，藏匿的钞票中含有大约5%的真实钞票，因此整个藏匿的钞票包含大约50000个不同的序列号
请注意，样本中频率的分布用于推断整个存储库中的分布。这实际上是你引用的第二篇论文中提到的"特别"(你的话)方法之一("基于采样的不同值数量估计(..)")：
参数估计器背后的思想是将概率分布拟合到 观察到不同属性值的相对频率
还要注意，HyperLogLog和类似方法的结果对样本在其值上的分布完全不敏感。但你的最终估计显然在很大程度上取决于它！
我的建议是：使用您选择的方法(如HyperLogLog)来计算样本中不同值的数量，然后使用"基于采样的估计"中的一种方法来估计整个多集中的值的数量，或者利用你对多集分布的先验知识来计算估计值(也许你看到了造假者的印刷机，你知道它只能打印一个序列号)
引文搜索是一件很棒的事情。我对这两个问题不是很熟悉，所以这篇论文可能不是你的意思。至少他们肯定会谈论HyperLogLog及其与问题的关系，所以也许它会满足你的好奇心。
离散元素问题的一种优化算法