kaf*_*fka 5 algorithm data-structures
HyperLogLog 估计多重集的基数。是否可以扩展它以处理多个多重集？比如，它不仅支持查询estimateCardinality()，还支持estimateCardinality(multiset_id)。我试图避免为每个 multiset_id 使用 HyperLogLog 值字典。
有没有另一种方法（数据结构）来实现这一目标？
当您有大量基数差异较大的多重集时，以下想法可能会有所帮助；即，有的尺寸大，有的尺寸小。它不需要你提前估计哪个会小，哪个会大。
您可以构建一个线性概率计数器，只需稍加改动。原始数据结构的每个位置都有一个（逻辑）布尔值。在这里，每个位置本身就是一个经典集合。而不是设置一点
insert(element)
op 如果它落在这个位置，您将插入id到集合中
insert(element, id)
您可以采取一些常识性技巧来节省空间。例如，您可以决定，如果id出现在 bin 的特定部分中，则它不会存储在 bin 集中，而是存储在所有 bin 上的单独位图中。
总的来说，如果您同时拥有小型和大型集，您最终会得到以下结果：
每个大集合的位图（对于您的计数器想法字典来说，每个项目的成本相同）
每个小集合的一些位集合中的条目（可能比您的计数器字典字典小得多）
由于对于特定的多重集，数据结构可以从后者切换到前者 - 它可能会节省相对于计数器思想字典的空间，这可能被认为是过早的悲观。
YMMV。