1

我爱上了概率数据结构。对于我目前的问题，似乎 count-min-sketch 结构几乎是正确的候选者。我想使用 count-min-sketch 来存储每个 ID 的事件。

假设我确实有以下

Map<String, Int> {
   [ID1, 10],
   [ID2, 12],
   [ID2, 15]
}

如果我使用 count-min-sketch，我可以通过 ID 查询数据结构并检索 ~counts。

问题

实际上，我对所有 ID 的平均出现次数感兴趣，在上面的示例中为：12,33。如果我使用的是 count-min，那么似乎我需要存储一组 ID，然后遍历该组并查询每个 ID 的 count-min 并计算平均值。有没有不存储所有 ID 的改进方法？理想情况下，我只想立即检索平均值而不记住所有 ID。

希望有道理！？

4

1 回答 1

1

如果您知道条目数和不同条目数，您应该能够计算平均计数：

averageCount = totalNumberOfEntries / numberOfDistinctEntries

正确的？并且要计算不同条目的数量，您可以使用例如HyperLogLog。您已经在问题中添加了 hyperloglog 标签，所以也许您已经知道这一点？

于 2018-11-12T09:20:55.903 回答