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