快速检查交集是否为空(误报即可)

Question

我需要做很多检查，如果两个集合的交集(一个对于所有检查是相同的，另一个是改变的)是空的还是不是。

如果检查表明(在少量检查中)它不是空的，这是可以的，但它是空的(可以有更精确的第二个过滤步骤)，所以误报是可以的。这是不允许的，我过滤掉了一些明确有非空交叉点的东西，所以假阴性是不可以的。

所以，只有一个场景：

{A,B,C,D} <-> {D,E,F} => true (交集中的D)，绝不允许为false

{A,B,C} <-> {D,E,F} => false (无交集)，也可以在少量检查中返回true

对于单个元素，我会使用bloom filter，但是对于一组元素，我找不到类似的方法，bloom filter逐个元素检查可能是一个可行的选择，但我正在寻找更好的方法。

Answer 1

非常感谢你的回答，帮助我想出了一个很好的解决方案，并解决了问题。

这个想法大部分都很原始，但已经足够了。

我创建了两个位集，一个用于变化集，另一个用于固定集。集合的每个元素被散列为一位(例如，对于1到64中的较长的一位)，然后组合成一个集合(主要是带有k=1的布隆-位集)。

要检查是否存在非空的交集，我只需要将两个位集与位加运算结合起来，并检查结果是否不是0。

假阳性率会更差(我认为没有计算过)，但对于我的情况来说已经足够好了。

示例：

A、B、C => 0000100010100000

B、D、F => 0100000010000100

0000000010000000 != 0 => true

Answer 2

一种优化是保留一个列表(用于快速查找的数组)，其中包含每个集合的最小/最大值。然后，首先检查列表中是否有重叠。如果不是，->返回false -不需要进一步的检查。

S1: a b c
S2:       d e f

S1 and S2 -> false (no overlap)

如果集合是排序的，并且它们确实重叠，则只需检查重叠区域。

S1: a b c d e
S2:       d e f g h

Only check the 'd e' region

如果您需要检查两个以上集合的交集，请首先尝试找到两个不重叠的集合。如果找到->，则返回false。如果不是，只检查所有这些集合的重叠区域(集合越多，重叠区域越小)。

S1: a b c d e
S2:       d e f g h
S3:             g h i

S1 and S2 and S3 -> false (S1 and S3 do not overlap)

如果大多数集合跨越很大的范围，您可以使用另一个选项：

假设元素的最大数量是6400 (对于本例)，每个元素都是，或者可以转换为整数1-6400。

对于每个集合，可以创建一个较小的位图(64位无符号整数)，其中一个位代表100个项目。

例如：

S1: 1,23,80,312,340
S2: 160,184,450
S3: 230,250,340

S1 bitmap: 100100..
S2 bitmap: 010010..
S3 bitmap: 001100..

S1 and S2 -> false
S1 and S3 -> true, only check range 301-400
S1 and S2 and S3 -> false

当然，您可以使用一个小于100的数字(最好是2的幂，这样您就可以快速设置相应的位)并使用多个uint64。

这甚至可以在多个级别上完成(取决于您愿意使用的内存/存储空间量)。例如，首先对一个64位整数进行真正的快速检查(需要一个CPU周期，使用SQL可以很容易地完成)。仅对于那些匹配的，检查第二个级别，可能包含4，8或16个uint64，每个位代表较小的值范围(使用SSE/AVX寄存器也可以非常快)。如果它们仍然匹配，则执行更深层次的检查，但仅针对与结果中的设置位相对应的范围。

Answer 3

你提到你正在用sql做这件事。所以我们有这样的smth：

第一个表格包含要检查的集合，第二个表格由要检查against

• ProbablyChangedSets (ElemId int16, SetId int, primary key(ElemId, SetId))：的集合组成

我很好奇这样的查询性能是不是还不够？

-- sets with intersections
select distinct
   cs.SetId
from ProbablyChangedSets cs
join PatternSet s on
    cs.ElemId = s.ElemId

-- |cs| = setCount * avgSetSize = 10^8 * 10 = 10^9
-- |s|  = avgSetSize = 10
-- numberOfComparisons ~= 10^9 * 10 = 10^10, comparisonComplexity = O(1)

有了足够的并行化，它将是非常快的-它是几秒钟。

或者您的检查是连续的，并且您需要优化单个检查操作？