对于多个集合是否有类似于HyperLogLog的结构？

Question

HyperLogLog估计多集的基数。是否可以将其扩展到处理多个集合？例如，它不只是支持查询estimateCardinality()，而是支持estimateCardinality(multiset_id)。我试图避免为每个HyperLogLog值创建一个multiset_id值字典。

还有其他方法(数据结构)来实现这一点吗？

Answer 1

如果您有大量的基数变化很大的多线程，那么下面的想法可能会有所帮助；也就是说，有些具有较大的大小，而有些则具有较小的大小。它不要求你预先估计哪些是小的，哪些是大的。

您可以构建一个线性概率计数器，只需做一个小小的更改。原始数据结构在每个位置都有一个(逻辑)布尔值。在这里，每个职位本身就是一个分类集。而不是在

insert(element) 

如果它落在此位置，则将id插入到

insert(element, id)

有一些常识的技巧，你奥德做的，以节省空间。例如，如果id出现在垃圾箱的某一小部分，那么它不是存储在bin集合中，而是存储在所有垃圾箱上的一个单独的位图中。

总之，如果您同时拥有小集和大集，您将得到以下结果：

• 每个大集合的位图(这是您的计数器词典的每个项目的相同成本)。
• 某些位集合中每一个小集合中的条目(可能比您的计数器字典概念小得多)

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

YMMV