是否可以对hyperloglog进行重复数据删除,以便添加和删除元素将产生相对正确的唯一计数？

Question

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

例如

add key1
delete key1
add key1

应该给出1的唯一计数

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

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

Answer 1

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

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

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

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

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