您的位置: 首页  >  文章  >  一种快速求集合交集个数上限的方法

一种快速求集合交集个数上限的方法

分类: 文章 • 2024-05-01 12:55:17

简介

介绍一个新的数据结构“Cardinality Filter”来快速计算一组交集的大小上限。且期望的时间复杂度为O(|A|+|B|w)，其中w表示字节大小。

动机

很多时候我们求交集并不在意交集的元素是什么，而是在意交集的个数是多少，比如在文本挖掘的top-k查询处理。
一种快速求集合交集个数上限的方法

在上图中，有多个文档（如”DOOR”,”DRIVING”等），给定一个查询（可能是一个文档，也可能是一串单词集合），求与它交集最多的前K个文档。显然在这里我们并不关注每个文档与它的交集元素是什么，而是关注每个文档与它的交集个数是多少。因此可以应用本文介绍的“Cardinality Filter”方法来加速top-k查询问题。

在该问题中，假设A为某个文档，B为查询文档，threshold为第K大的交集个数，则问题则变为求 |A ∩ B| > threshold,但实际上绝大多数|A ∩ B| ≪ threshold，在测试中有多达80% |A ∩ B| < 0.05 × threshold。
因此我们可以利用求出|A ∩ B|的上限来加速这个问题，即|A ∩ B| ≦ Upper bound of |A ∩ B| ≦ threshold。这样子我们将跳过绝大数的|A ∩ B|的确切计算。

Cardinality Filters

一种快速求集合交集个数上限的方法

所谓的Cardinality Filters就是将原有的A,B集合在X的定义域中通过某种映射方法映射成Φ(A)和Φ(B)，将 |A ∩ B| 问题转为 |Φ(A) ∩ Φ(B)|。
Cardinality Filters有两种实现，Single Cardinality Filter（SCF）和 Recursive Cardinality Filter（RCF）。

SCF - Single Cardinality Filter

SCF定义Φ(A) = ( h(A), c(A) )，
其中h(A)表示hash后的值，而c(A)表示hash冲突里面非最小的值。注意这里h(A)是一个长度为⌈ |X| / N ⌉ 的bit序列，c(A)为int数组。下面用个例子来说明。
一种快速求集合交集个数上限的方法

如图N=3，hash到[0,4]。
A集合里有元素{7,8,10,12,14}，通过hash分别映射到{2,0,2,4,4}，显然发生了冲突，即2(7,10),4(12,14)，故按照定义，这里h(A)={0,2,4},Φ(A)={10,14}。
同样的在B集合里有元素{0,2,3,5,7,10,11,14}，通过相同的hash分别映射到{1,2,4,0,2,2,1,4}，这里的冲突为1(0,11),2(2,7,10),4(3,14)，所以这里h(B)={0,1,2,4},Φ(A)={7,10,11,14}。
故这里 |Φ(A) ∩ Φ(B)|= |h(A) ∩ h(B)| + |c(A) ∩ c(B)| = 3 + 2 = 5 。
而 |A ∩ B| = 3 ， 故 Φ(A) ∩ Φ(B) 符合 A ∩ B 的上限。

直观上，之所以Φ(A) ∩ Φ(B)会是A ∩ B的上限，有如下两点：

  • 当不同的元素hash到同一值且未值上最小时（如图A中的8和B中的5都被hash到0），交集会额外多算；
  • 图中14被重复计算了2次，|h(A) ∩h(B)| 和 |c(A) ∩ c(B)| 都加了一次。

下面给出SCF的严格定义：
设X为全域（A, B ⊂ X），设H为hash值空间 H={ 0, 1,…,N, ⌈ |X| / N ⌉ - 1}。
有 Φ: 2X−>(2H,2X) : Φ(A) = (h(A), c(A)) (A ⊂ X)
其中 h(A) = { h(x) | x ∈ A }，值域为{0, ⌈ |X| / N ⌉ - 1 }.
c(A) = { y∈A | (∃x∈A) (h(x) = h(y), x < y) }。
得： |A∩B| ≦ |Φ(A)∩Φ(B)| := |h(A)∩h(B)| + |c(A)∩c(B)|

其中 |h(A)∩h(B)|的计算可以通过Bit-wise AND操作（hash后为bit序列），而|c(A)∩c(B)|的计算可以通过简单的方法来计算，如linear merge algorithm或者hash或者二分。

SCF的几点性质

  • 对于任意 A, B ⊆ X, |A ∩ B| ≤ |Φ(A) ∩Φ(B)|.

    证明：
    |A ∩ B| = |A ∩ B ∩ c(A) ∩ c(B)| + |(A ∩ B) \ (c(A) ∩ c(B))|,
    |Φ(A) ∩ Φ(B)| = |c(A) ∩ c(B)| + |h(A) ∩ h(B)|.
    所以要证 |A ∩ B| ≤ |Φ(A) ∩Φ(B)| 等价于证明：
    |A ∩ B ∩ c(A) ∩ c(B)| + |(A ∩ B) \ (c(A) ∩ c(B))| < |c(A) ∩ c(B)| + |h(A) ∩ h(B)|.
    显然有 |A ∩ B ∩ c(A) ∩ c(B)| ≤ |c(A) ∩ c(B)|,
    因此现在只需证明 |(A ∩ B) \ (c(A) ∩ c(B))| < |h(A) ∩ h(B)|.
    x ∈ (A ∩ B) \ (c(A) ∩ c(B))
    ⇒ x ∈ A ∧ x ∈ B
    ⇒ h(x) ∈ h(A) ∧ h(x) ∈ h(B)
    ⇒ h(x) ∈ h(A) ∩ h(B).
    且假设x < y 且 y ∉ c(A) ∩ c(B), 所以 y ∉c(A) 或者 y ∉ c(B).
    若 y ∉c(A)，说明y是在hash(y)里最小的数，即不存在z ∈ A，使得 z < y and h(z) = h(y).
    若 y ∉c(B)，同理，则不存在z ∈ B， 使得 z < y and h(z) = h(y).
    因此，在 (A ∩ B) \ (c(A) ∩ c(B))里的任意两数x,y, 有 h(x) ≠ h(y).
    通过上述分析，对于 x ∈ (A ∩ B) \ (c(A) ∩ c(B))，都有唯一值h(x)与之对应，即说明了 |(A ∩ B) \ (c(A) ∩ c(B))| = |h((A ∩ B) \ (c(A) ∩ c(B)))|，
    而又有且 h(x) ∈ h(A) ∩ h(B), 所以h符合内射性(injectivity)，固 h( (A ∩ B) \ (c(A) ∩ c(B)) )是 h(A) ∩ h(B)的子集。
    所以， | h( (A ∩ B) \ (c(A) ∩ c(B)) ) | ≤ |h(A) ∩ h(B)|
    所以， | (A ∩ B) \ (c(A) ∩ c(B)) | ≤ | h(A) ∩ h(B)|.
    而 |A ∩ B ∩ c(A) ∩ c(B)| ≤ |c(A) ∩ c(B)|, 得出结论：
    |(A ∩ B)| = |A ∩ B ∩ c(A) ∩ c(B)| + |(A ∩ B) \ (c(A) ∩ c(B))|
    ≤ |c(A) ∩ c(B)| + |h(A) ∩ h(B)| = |Φ(A) ∩Φ(B)|. 得证。

  • c(A)的期望size最多为 ：N|A|22|X|

    证明：
    令 β 是对应于h（A）的比特数组，其长度为|H| = ⌈|X|/N⌉。
    hash函数将任意数x hash到任意bit位上的概率为 1|H|
    某一位bit上没有数的概率为：(1−1|H|)|A|
    因此 β 上bit上的有效位数为：|H|(1−(1−1|H|)|A|)
    所以c(A)的期望size为：
    |A| − |h(A)|
    =|A|−|H|(1−(1−1|H|)|A|)
    ≤|A|−|H|(1−(1−|A||H|+|A|22|H|2))
    =|A|22|H|≤N|A|22|X|
    【有不等式：(1−ϵ)n≤1−nϵ+n2ϵ22】

  • 应用SCF，对于集合A预期空间使用量最多为：⌈|X|N⌉+wN|A|22|X| bits.

    证明：
    |h(A)|+|c(A)|=⌈|X|N⌉+wN|A|22|X|

  • 应用SCF计算 |Φ(A)∩Φ(B)|的时间复杂度为：O(|X|Nw+N(|A|2+|B|2)|X|)。
    证明：
    对hash后的 βA 和βB 进行AND操作的时间复杂度为：O((|X|/N) · (1/w))，即O(|X|Nw)
    而用 linear merge algorithm计算 |c(A) ∩ c(B)| 时间复杂度为：
    O(|c(A)|+|c(B)|)=O(N(|A|2+|B|2)2|X|)=O(N(|A|2+|B|2)|X|)
    相加即得证。
  • The expected approximation ratio of SCF is at most 1+N|A||B||X||A∩B|.

RCF - Recursive Cardinality Filter

Recursive意为递归，故RCF顾名思义就是递归版本的SCF，递归的地方就是c(A)，在SCF中我们可以得到 (h1(A), c1(A))，这里我们继续对得到的c1(A)应用SCF，则可以得到(h2(A), c2(A)),继续递归下去….
定义递归层次为L，这样就可以得到 (h1(A), c1(A))， (h2(A),c2(A))… (hL(A),cL(A))
所求集合上限则为: |Φ(A)∩Φ(B)|=∑Li=1|hi(A)∩hi(B)|+|cL(A)∩cL(B)|

一种快速求集合交集个数上限的方法

下面给出RCF的严格定义：
对于L层递归，有：
Φ(A)=(H1(A),H2(A),...,HL(A),CL(A))，其中
Hi(A)=hi(ci−1(ci−2(...c1(A)...))),
Ci(A)=ci(ci−1(...c1(A)...)), for i = 1, 2, … , L.

Φ(A)∩Φ(B)=(H1(A)∩H1(B),H2(A)∩H2(B)...,HL(A)∩HL(B),CL(A)∩CL(B))
|Φ(A)|=∑Li=1|Hi(A)|+|CL(A)|

RCF的几点性质

  • 对于任意 A, B ⊆ X, |A ∩ B| ≤ |Φ(A) ∩Φ(B)|.
  • 设 L=⌈logmax|A|,|B|⌉，r是一个比1大的常数，
    Ni=⌊2i−1|X|rmax|A|,|B|⌋, (i=1, 2, … , L ),
    对于L层的RCF，计算| Φ(A) ∩ Φ(B) |的时间复杂度为O(|A|+|B|w)。
    【具体证明见论文。】

参考资料

论文《Faster Upper Bounding of Intersection Sizes》,文中部分结论证明见论文。

相关推荐