algorithm - 多个多重集是否有类似 HyperLogLog 的结构？

Question

HyperLogLog 估计多重集的基数。是否可以扩展它来处理多个多重集？比如，它不仅支持查询 estimateCardinality()，还支持 estimateCardinality(multiset_id)。我试图避免为每个 multiset_id 使用 HyperLogLog 值的字典。

是否有另一种方式(数据结构)来实现这一点？

Answer 1

当您有大量基数差异较大的多重集时，以下想法可能会有所帮助；也就是说，有的尺寸大，有的尺寸小。它不需要你事先估计哪个小哪个大。

您可以构建一个 Linear Probabilistic Counter , 有一个小的变化。原始数据结构在每个位置都有一个(逻辑) bool 值。在这里，每个位置本身就是一个经典集。而不是在

上设置一点

insert(element) 

op 如果它落在这个位置，你可以将 id 插入到

的集合中

insert(element, id)

您可以采用一些常识性技巧来节省空间。例如，您可以决定，如果 id 出现在 bin 的特定部分中，那么它不会存储在 bin 集中，而是存储在所有 bin 的单独位图中。

总的来说，如果您同时拥有小型和大型集，您最终会得到以下结果:

• 每个大集合的位图(这与您的计数器字典想法的每项成本相同)

• 每个小集合的一些位集合中的条目(可能比您的计数器字典想法小得多)

由于数据结构可以针对特定的多重集从后者切换到前者 - 它可能会节省相对于计数器字典想法的空间，这可能被认为是过早的悲观化。

YMMV.