如果我想在可以添加和删除的元素列表中获取唯一计数，有没有办法做到这一点？
例如
add key1
delete key1
add key1
应该给出一个唯一的计数 1
但是如果我有一个 2 hll 一个用于删除和一个用于添加的天真方法，它返回 0？
有没有办法可以在 hll 中删除密钥？
问问题
356 次
2 回答
0
我看不到如何使用超日志日志来做到这一点，但我确实看到了如何使用效率较低的基数估计器来做到这一点。
这是一个简单的基数估计器，您可以在http://www.cse.unsw.edu.au/~cs9314/07s1/lectures/Lin_CS9314_References/fm85.pdf中找到它。计算每个元素的哈希值。保留最小的m哈希值。使用m第 th 个哈希值的大小来估计整个集合的基数。（让我们忽略哈希冲突。）
现在这里是处理一些删除的改编。保留最小的2m哈希值。使用m'th 最小的大小来估计整个集合的基数。如果要删除哈希元素，只需将其从集合中删除即可。只要您的集合的大小不下降大约 2 倍，这应该可以很好地工作。
如果你需要处理更多？添加“幽灵”元素的想法。当您删除一个哈希值时，在2m+1预期的第 'th 个哈希值的位置添加一个“幽灵”哈希值。当你删除一个真实的哈希值时，每个“幽灵”元素都有一个随机的机会被删除，它与被删除的真实元素的比例相匹配。如果删除了重影，则插入更多内容。如果你插入了足够多的幽灵变得太大而不能进入最小的2m，你让它像任何其他值一样脱落。
生成的算法将需要更多内存，但会处理添加和删除。即使您的大部分数据被删除，它也应该相当准确。
于 2018-06-01T17:31:38.470 回答
0
您可以保留一个单独的 HyperLogLog 来计算删除的项目，并减去以获得最终计数。但是，这种方法有一些注意事项： 1. 根据您的应用程序，可能仅在以前看到过该值时才需要计算删除，这实际上是不可能知道的。2. 精度会降低，具体取决于添加和删除元素的模式。
于 2018-06-02T17:49:28.110 回答