在Redis中交叉巨大HyperLogLog的最佳方法

Question

问题很简单:我需要根据Redis的表示找到最佳策略来实现准确的HyperLogLog联合 - 这包括在导出数据结构以供其他地方使用时处理它们的稀疏/密集表示.

两个策略

有两种策略,其中一种似乎要简单得多.我已经看过实际的Redis源代码了,我遇到了一些麻烦(在我自己的C中并不大),从精确和高效的角度来看,使用内置的结构/例程或开发自己的内容是否更好.对于它的价值,我愿意牺牲空间和某种程度上的错误(stdev + -2%)以追求效率与极大的集合.

1.包容性原则

到目前为止,两者中最简单的 - 基本上我只是将无损联合(PFMERGE)与此原理结合使用来计算重叠的估计.在许多情况下,测试似乎表明这种运行是可靠的,尽管我无法准确处理非常高的效率和准确性(某些情况下会产生20-40%的错误,这在这个用例中是不可接受的).

基本上:

aCardinality + bCardinality - intersectionCardinality

或者,在多组情况下......

aCardinality + (bCardinality x cCardinality) - intersectionCardinality

似乎在许多情况下都能很好地准确地工作,但我不知道我是否相信它.虽然Redis有许多内置的低基数修饰符,旨在规避已知的HLL问题,但我不知道野生不准确(使用包含/排除)的问题是否仍然存在大量差异很大的问题......

2. Jaccard Index Intersection/MinHash

这种方式似乎更有趣,但我的一部分感觉它可能与Redis的一些现有优化计算重叠(即,我没有从头开始实现我自己的HLL算法).

通过这种方法,我将使用MinHash算法的随机抽样箱(我不认为LSH实现值得麻烦).这将是一个单独的结构,但通过使用minhash获取集合的Jaccard索引,您可以有效地将union基数乘以该索引以获得更准确的计数.

---

问题是,我不太熟悉HLL,虽然我很想深入研究Google论文,但我需要在短期内实现可行的实施.有可能我忽略了Redis现有优化的一些基本考虑因素,或者在算法本身中,它允许计算上便宜的交叉点估计具有相当宽松的置信区间.

因此,我的问题:

如果我愿意牺牲空间(并且在很小程度上,精确度),如何使用redis最有效地获得N个巨大(数十亿)集的计算上便宜的交叉估计？

Answer 1

前段时间读过这篇论文。可能会回答您的大部分问题。包含原则不可避免地会导致大量集合的误差范围增加。最小哈希方法将是可行的方法。

http://tech.adroll.com/media/hllminhash.pdf