问题很简单:我需要根据 Redis 的表示找到最佳策略来实现准确的 HyperLogLog 联合——这包括在数据结构导出以供其他地方使用时处理它们的稀疏/密集表示。
两种策略
有两种策略，其中一种似乎简单得多。我查看了实际的 Redis 源代码，我遇到了一些麻烦(我自己在 C 中并不大)弄清楚从精度和效率的角度来看使用他们的内置结构/例程还是开发我自己的更好.对于它的值(value)，我愿意牺牲 空间 和某种程度的错误 (stdev +-2%) 来追求极大集合的效率。
1。包容原则
到目前为止，这是两者中最简单的一个——本质上，我只是将无损联合 (PFMERGE) 与此原理结合使用来计算重叠的估计值。测试似乎表明在许多情况下这种运行可靠，尽管我无法准确处理野外效率和准确性(某些情况下会产生 20-40% 的错误，这在这个用例中是 Not Acceptable )。
基本上:
aCardinality + bCardinality - intersectionCardinality
或者，在多组的情况下......
aCardinality + (bCardinality x cCardinality) - intersectionCardinality
似乎在很多情况下都非常准确，但我不知道我是否相信它。虽然 Redis 有许多内置的低基数修饰符，旨在规避已知的 HLL 问题，但我不知道在大小差异很大的情况下是否仍然存在严重不准确的问题(使用包含/排除)...
2。 Jaccard 索引交集/MinHash
这种方式看起来更有趣，但我的一部分感觉它可能在计算上与 Redis 的一些现有优化重叠(即，我不是从头开始实现我自己的 HLL 算法)。
通过这种方法，我将使用 MinHash 算法对 bin 进行随机抽样(我认为 LSH 实现不值得这么麻烦)。这将是一个单独的结构，但通过使用 minhash 获取集合的 Jaccard 索引，您可以随后有效地将联合基数乘以该索引以获得更准确的计数。
问题是，我不是很精通 HLL，虽然我很想深入研究 Google 论文，但我需要一个可行的短期实现方案。有可能我忽略了 Redis 的现有优化或算法本身的一些基本考虑因素，这些考虑因素允许计算成本低廉的交集估计具有相当宽松的置信区间。
因此，我的问题:
如果我愿意牺牲空间(并且在小程度上，准确性)，我如何使用 redis 最有效地获得 N 大(十亿)组的计算成本低的交集估计？
最佳答案
前段时间读过这篇论文。可能会回答你的大部分问题。包含原则不可避免地会在大量集合中加入误差范围。 Min-Hash 方法将是可行的方法。
关于hash - 在 Redis 中交叉巨大的 HyperLogLogs 的最佳方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30106633/