algorithm - 是否有可能对 hyperloglog 进行重复数据删除，以便添加和删除元素会产生相对正确的唯一计数？

Question

如果我想获取可添加和删除的元素列表中的唯一计数，有没有办法做到这一点？

例如

add key1
delete key1
add key1

应该给出一个唯一的计数 1

但是如果我有一个 2 hll 的简单方法，一个用于删除，一个用于添加，它返回 0？

有没有办法可以在 hll 中删除重复键？

Answer 1

我不知道如何使用 hyper log 日志来做到这一点，但我知道如何使用效率较低的基数估计器来做到这一点。

这是一个简单的基数估计器，您可以在 http://www.cse.unsw.edu.au/~cs9314/07s1/lectures/Lin_CS9314_References/fm85.pdf 中找到它.计算每个元素的哈希值。保留最小的 m 哈希值。使用第 m 个哈希值的大小来估计整个集合的基数。 (让我们忽略哈希冲突。)

现在这里是一个处理一些删除的改编。保留最小的 2m 哈希值。使用第 m 个最小的大小来估计整个集合的基数。如果要删除散列元素，只需将其从集合中删除即可。只要您的集合大小不下降大约 2 倍，这应该会很好地工作。

如果您需要处理更多？添加“幽灵”元素的想法。删除散列值时，在第 2m+1 散列值预期所在的位置添加“幻影”散列值。当你删除一个真实的哈希值时，每个“幽灵”元素都有一个随机的机会被删除，它与被删除的真实元素的比例相匹配。如果删除了重影，则插入更多。如果你插入的足够多以至于重影变得太大而不能在最小的 2m 中，你让它像任何其他值一样脱落。

生成的算法将需要更多内存，但会处理添加和删除。即使您的大部分数据被删除，它也应该相当准确。