近似重复数据(near duplicate data)是具有很高相似度但又不完全相同的数据.产生重复数据的原因很多, 例如印刷错误、镜像页面和完全或部分剽窃的文档等.相似连接(similarity join)是一种有效查找数据集中相似记录对的方法, 因而在数据清理、数据集成和近似网页去重等领域得到了广泛的应用^[1-24].例如:在数据清理中, 通过相似连接算法, 可以为不同数据源提供准确、一致的数据; 在数据集成中, 通过相似连接对命名实体识别进行归类; 在镜像页面中, 使用相似连接抓取相似网页, 提高网页搜索引擎的执行效率.

目前, 相似连接主要有两种类型:一是基于相似阈值的相似连接^{[1, 2, 4-9, 10-23]}, 即, 找出数据集中相似值不小于阈值(由用户自定义)的记录对; 另一种是Top-k相似连接^[3], 即, 找出数据集中相似度最高的前k个记录对, 其中, k值由用户自己定义.

基于阈值的相似连接算法可分为两类^[14]:第1类使用过滤技术过滤掉多余的候选对, 例如AllPair^[1], PPJoin^[2], EDJoin^[10], QChunk^[8], VChunk^[11]和AdaptJoin^[4]等, 也有使用其他的签名(signature), 例如PartEnum^[18], PassJoin^[9]和FastSS^[15]; 第2类算法利用特殊的树形索引来计算连接的结果, 典型的有TrieJoin^[13].

在基于相似阈值的相似连接算法中, 阈值需要用户自己定义.在实际应用中, 相似度阈值往往与数据集特性相关, 因此会出现面对新的数据集无法确定合适阈值的问题.此外, 在一些应用中, 用户有时关心的不是相似阈值有多大, 而是记录集中哪几个记录对最相似.为此, 文献[3]提出了一种Top-k相似连接算法Topk-join.与基于阈值的相似连接算法相比, Topk-join避免了因输入阈值太大而得到空的结果, 或者输入阈值太小而运行时间过长的问题.

Topk-join使用事件驱动(event driven)框架来查找数据集中最为相似的k对记录, 算法中最为核心的概念是前缀事件(prefix event).前缀事件是一个三元组〈r, p_r, sp_r〉, 其中, r表示记录, p_r表示记录中待处理Token的位置, sp_r是该记录与数据集中所有其他记录相似度的最大值.Topk-join使用临时结果堆保存当前最相似的k个记录对; 使用前缀事件堆存储所有前缀事件, 并每次弹出具有最大sp_r值的前缀事件进行处理.文献[3]证明:当程序结束时, 临时结果堆中一定存储着最相似的前k个记录对.本文第2节将会对Topk-join做更为详细的介绍.

与基于阈值的相似连接算法PPJoin^[2]相比, 在相似阈值未知的情况下, Topk-join算法具有更好的性能.但是我们在研究中发现, Topk-join存在如下性能问题.

(1)为了减少重复计算, 算法执行过程中生成的每一个候选记录对都需要查找哈希表, 从而导致哈希查找代价过大;

(2)每次前缀事件只处理记录的一个Token, 使得临时结果集逼近真实结果的速度较慢, 同时造成前缀事件和临时结果堆的维护代价过大.

针对上述问题, 本文提出了一种基于Token批处理的Top-k相似连接算法Opt-join.新算法通过调换哈希查找与过滤操作位置以及对Token进行批处理操作, 显著提高了Top-k相似对的查找速度.本文的主要贡献有:

·理论证明了调换哈希查找和过滤操作位置能够保证算法正确性.以此为基础, 在Opt-join中对候选记录对先进行过滤操作(位置过滤和后缀过滤), 随后再进行哈希查找.在大量减少哈希查找数量的同时, 还提高了过滤操作的过滤能力;

·根据数据集特性, 设计了有效选择Token批处理长度的方法.通过在事件驱动框架中集成Token批处理技术, 加快了相似度阈值的迭代速度, 并减小了前缀事件和临时结果堆维护的代价;

·分别实现了Opt-join和Topk-join算法, 并基于真实数据集对两种算法进行了全面的实验性能对比.实验结果显示:与Topk-join算法相比, Opt-join的Size过滤和位置过滤的能力均得到了显著提高, 堆处理的代价极大地降低, 哈希查找的代价减小了1倍~2倍, 并最终取得了1.28~3.09的加速比.在数据长度增加或k值增加时, Opt-join的性能优势会变得更加明显.

本文第1节介绍背景知识.第2节给出Topk-join算法的执行过程.第3节详细讨论本文提出的两个优化策略.第4节是实验和结果分析.最后, 第5节总结全文.

1 问题定义和背景知识 1.1 问题的形式化定义

有限集U为Token的集合.O为定义在U上的一个全序, 按照Token的文档频率(document frequency)升序排列.记录r为若干Token的集合且这些Token在r中按照O进行排列.给定两个记录r和s, 相似函数sim(r, s)返回一个[0, 1]区间的相似值, 该值越大, 表示记录r和s越相似.我们用|r|表示记录r中Token的个数.本文讨论的相似函数及计算公式见表 1.

表 1中给出的4种相似度函数有其内在的联系^[2].具体地, 给定某种相似函数和相似度阈值θ, 若sim(r, s)≥θ, 那么一定有O(r, s)≥∂.其中, O(r, s)表示记录r和s的Overlap相似度, ∂是通过相似函数计算的Overlap相似度阈值.表 2给出了Jaccard相似度、余弦相似度和Dice相似度中Overlap相似度阈值的计算公式.如非明确说明, 本文后面部分都以Jaccard相似度函数为例进行讨论.

不同于传统基于相似度阈值的连接操作, Top-k相似连接定义如下.

定义1(Top-k相似连接).给定两个记录集R={r₁, r₂, …, r_n}和S={s₁, s₂, …, s_m}、相似函数sim和用户定义的参数k, Top-k连接找出R×S中最相似的前k个记录对, 即{(r, s)_i|(r, s)_i > (r, s)_j, (r, s)∈R×S, i∈[1, k], j∉[1, k]}.

与文献[3]类似, 本文重点考虑R=S的情况, 即, 同一数据集中记录项之间的自连接.

1.2 过滤技术

现有的相似连接算法使用过滤技术来减少需要精确计算相似度的候选记录对个数, 目前常用的过滤技术如下所示.

(1)前缀过滤(prefix filtering)

传统的相似连接将记录中所有Token插入到倒排索引(inverted index)中, 通过扫描倒排索引生成候选记录对.这种方法的缺点是索引表过于庞大, 同时, 当记录集中某一个Token出现频率较高时, 会生成大量重复的候选记录对.为解决上述问题, 文献[6]在对记录集进行预处理(按Token的文档频率升序排列)的基础上, 提出了前缀过滤算法.前缀过滤算法有效地解决了索引表过大和候选对大量重复的问题, 并将插入倒排索引表的Token数由|r|减小到了|r|-∂+1.

定理1(前缀过滤)^{[6, 16]}.给定记录r和s, 如果sim_O(r, s)≥∂, 那么记录r的(|r|-∂+1)-前缀与记录s的(|s|-∂+1)-前缀至少有一个公共的Token值.表 3给出了不同相似函数下记录前缀的长度.

(2)长度过滤(size filtering)^[2]

记录间的相似度与记录的长度存在一定的关系.如果两个记录比较相似, 它们的长度也比较接近.例如, 在Jaccard相似度下, 如果sim_J(r, s)≥θ, 那么记录r和s的长度关系见公式(1).

$\theta \cdot |r| \le |s| \le \frac{{|r|}}{\theta }$

(1)

表 4给出了不同相似度函数下记录的长度范围.根据r和s的长度关系, 可以过滤掉那些明显不满足条件的记录对.

(3)位置过滤(positional filtering)

前缀过滤的前提是记录集中每条记录Token都是有序的.在前缀过滤的基础上, 文献[2]利用Token在记录中的位置信息进一步减小候选对的数量.

定理2(位置过滤)^[2].给定两个Token按照全序O排列的记录r和s, 对于任意的Token e=r[i]=s[j], 它将记录r分为前缀部分$Prefix_r^i = r[1...(i - 1)]$和后缀部分$Suffix_r^i = r[i...|r|]$(s同理).如果sim_O(r, s)≥∂, 那么有:

$si{m_O}(Prefix_r^i,Prefix_s^j) + \min (|Suffix_r^i|,|Suffix_s^j|) \ge \partial $

(2)

(4)后缀过滤(suffix filtering)

根据前缀定理, 随着相似度阈值的增加, 前缀长度逐渐减小, 而后缀长度逐渐增大.位置过滤只针对记录的前缀, 而对于记录后缀却缺少有效的利用.为了进一步减小候选对数量, 文献[2]中提出了后缀过滤技术.

后缀过滤基于记录对的海明(Hamming)距离.任意记录对的海明距离可通过它们的Overlap相似度计算出来^[2].具体来说, 给定记录r和s, 如果sim_O(r, s)≥∂, 则dis_H(r, s)≤|r|+|s|-2∂, 其中dis_H(·, ·)计算两个记录的海明距离.记录r和s的最大海明距离(H_max)见公式(3).

${H_{\max }} = |r| + |s| - 2 \cdot \partial - (i + j - 2 \cdot si{m_O}(Prefix_r^i,Prefix_s^j))$

(3)

其中, ∂是Overlap相似度阈值, i和j分别表示记录r和记录s前缀中最后一个Token的位置, $si{m_O}(Prefix_r^i,Prefix_s^j)$表示前缀中的Overlap相似度值.

有了r和s的最大海明距离, 后缀过滤通过一个递归算法估算r和s的实际海明距(H_c), 具体算法见文献[2].当一个候选记录对的H_c > H_max时, 我们就可以将该记录对丢弃.

2 Topk-join算法

不同于传统的相似连接算法(例如AllPair^[1], PPJoin^[2]), Topk-join使用事件驱动框架来寻找记录集中最相似的前k个记录对^[3], 其中, 核心的概念是前缀事件.前缀事件是一个三元组〈r, p_r, sp_r〉, 其中:r表示记录; p_r表示下一个要插入到前缀中的Token的位置; sp_r是记录r与数据集中其他记录相似度值的上边界, 计算方法见公式(4).

$s{p_r} = 1 - \frac{{{p_r} - 1}}{{|r|}}$

(4)

算法执行过程中的临时结果也是一个三元组〈r, s, θ_rs〉, 其中, r和s均表示记录, θ_rs表示记录r和s的相似度值. Topk-join分别使用最大堆(E)和最小堆(T)保存算法执行过程中生成的前缀事件和临时结果.

Topk-join的执行框架如下:

(1)初始化前缀事件堆E(将sp_r=1的所有前缀事件插入到最大堆中)和临时结果堆T(任意k个记录对插入到最小堆中);

(2)取出E的堆顶元素〈r, p_r, sp_r〉.如果sp_r的值不小于T中堆顶元素〈r, s, θ_rs〉的相似值θ_rs(即sp_r≥θ_rs时), 使用位置p_r上Token查找倒排索引(inverted index)以生成候选记录对; 否则, 整个程序结束, 此时, 临时结果堆中的记录对即为Top-k记录对;

(3)计算新生成候选对的相似度$\theta _{rs}^ + $, 如果该值大于T堆顶的相似值θ_rs, 即$\theta _{rs}^ + > {\theta _{rs}}$, 则将该候选对和对应相似值插入到T中, 同时弹出T中的最小值, 以保证堆的大小为k;

(4)删除已处理完的前缀事件(T的堆顶元素), 生成相应记录的下一个前缀事件〈r, p_r+1, sp_r〉并插入T中, 继续执行步骤(2)和步骤(3).

算法1给出了Topk-join的伪代码.初始阶段, 将所有sp_r=1的前缀事件插入到事件堆E中; 选取记录集合的第1条记录和第2-k+1条形成k个记录对, 计算相应的相似值, 并将结果插入到临时结果堆T中(第1行).执行阶段, 首先取出前缀事件堆的堆顶元素(第3行), 比较上界值(sp_r)与临时结果堆的堆顶记录对相似度值, 判断程序是否结束(第5行).对新生成的候选对, 先查找其是否已存在于全局哈希表(H)中, 对查找不到的候选对进行过滤操作(第9行、第10行).最后, 对过滤不掉的候选对计算相似度值(第11行), 并更新全局哈希表、前缀事件堆、临时结果堆和倒排索引(第12行、第13行和第15行).

算法1. Topk-join(R, k).

输入:R为所有记录的集合; k表示要输出的相似对个数;

输出:最相似的前k个记录对.

1. Initialize prefix event heap E and result heap T.

2. WHILE E≠∅

3. 〈r, p_r, sp_r〉←E.pop(·);

4. sim_k=T[k].θ_rs;

5. IF sp_r≤sim_k

6. break;

7. ENDIF

8. Generate candidate pairs (r, s) via index search;

9. IF (r, s)∉H

10. Perform filtering (including size, positional and suffix filtering);

11. Compute the similarity of (r, s);

12. H←H∪(r, s);

13. Update the inverted index and T;

14. Calculate new similarity bound sp_r;

15. E.push(r, p_r+1, sp_r);

16. ENDIF

17. ENDWHILE

3 Top-k相似连接算法Opt-join

本节将讨论Topk-join中存在的两个重要性能缺陷, 并提出哈希查找优化策略和前缀批处理技术作为解决方案.通过在事件处理框架中结合这两种方法, 设计了一种新的相似连接算法Opt-join.

3.1 优化哈希查找 3.1.1 哈希查找的性能问题及解决方法

在事件驱动框架中, 两个记录的前缀中有几个重复Token值, 这两个记录组成的候选对就会被重复生成相应的次数, 从而导致同一个候选对可能会被验证多次.算法1中使用了一个全局哈希表(H)来避免候选对的重复验证, 主要设计思路是:对于生成的候选对, 首先查找全局哈希表(算法1第9行), 如果该候选对不在哈希表中, 则进行过滤操作(算法1第10行).对没过滤掉的候选对, 精确计算其相似度值(算法1第11行), 并将其插入到哈希表中(算法1第12行).若该候选对已经存在于哈希表中, 表示其已经被处理过, 不再需要重复计算.

哈希表的使用解决了候选对重复验证的问题, 但也不可避免地带来了哈希表查找的代价.通过记录哈希表的查找和插入过程, 我们统计了Topk-join花费在哈希操作上的时间代价.图 1给出了TREC数据集(详见实验部分)下程序总运行时间与哈希查找和插入时间的比较, 可以看到, 在哈希查找和插入上花费的时间占总时间的20%以上.造成这一情况的原因是:虽然每次哈希查找代价不大, 但每个新生成的候选对都需要查找哈希表, 因此当候选对总数很大时, 就会花费过多的时间.

以top-500查询为例, 程序在运行过程中总共生成2.15亿个候选对, 最终哈希表的大小为247万.在2.15亿个候选对中, 被哈希表过滤掉的候选对(即重复验证的候选对)为169万个, 只占到总数的0.8%, 而99%的候选对被其他过滤操作(包括长度、位置和后缀过滤)过滤掉.如果这些被过滤掉的候选对不经过哈希查找, 那么哈希表的代价就会极大地降低.

基于上述分析, 我们将哈希查找推迟到各种过滤技术之后进行, 见算法2.在程序执行过程中, 新生成的候选对先进行过滤, 过滤不掉的候选对再进行全局哈希表的查找.这样不仅避免候选对重复计算, 又减小了哈希代价.算法2用于替换算法1中的第9行~第13行.

算法2. Opt-hash(r, s).

1. Perform filtering operations (including size, positional and suffix filtering);

2. IF (r, s)∉H

3.  Compute the similarity of (r, s);

4. H←H∪(r, s);

5. Update the inverted index and T;

6. ENDIF

上述优化带来了一个新问题:在优化前, 过滤操作只在候选对第1次出现公共Token时才会被调用, 随后生成的重复候选对将会被全局哈希过滤掉, 所以, 过滤操作只执行1次.优化后, 每个公共Token生成的候选对都要进行过滤操作(位置过滤使用公式(2), 后缀过滤使用公式(3)).观察公式(2)和公式(3)可以发现, 位置过滤和后缀过滤均依赖于候选对前缀的Overlap值.要精确计算Overlap值, 需要每次扫描候选对的前缀, 这样将会花费更大的代价.为此, 我们考虑将候选对前缀的Overlap值($si{m_O}(Prefix_r^i,Prefix_s^j)$)置为1, 即, 使用公式(5)来代替公式(2)、使用公式(6)代替公式(3)来进行过滤, 避免对候选对前缀的重复扫描.

$1 + \min (|Suffix_r^i|,|Suffix_s^j|) \ge \partial $

(5)

${H_{\max }} = \left| r \right| + \left| s \right| - 2 \cdot \partial - (i + j - 2)$

(6)

容易看出:当前缀中Overlap值为1时, 使用公式(5)和公式(6)过滤算法均能正确执行.而当前缀Overlap值大于1时, 过滤算法的正确性则有待证明, 下面我们将讨论这一问题.

3.1.2 正确性证明

Topk-join算法使用Size过滤、位置过滤和后缀过滤来减少候选对的数量.Size过滤利用记录对的长度关系完成过滤, 因此, 第3.1.1节的优化对Size过滤没有影响.下面我们只需要证明位置过滤和后缀过滤在优化后的正确性.

观察1.在对候选记录对进行位置过滤的过程中, 公式(5)与公式(2)的正确性相同, 且公式(5)具有更强的过滤能力.

证明:容易看出:当第1次生成候选对时, 记录对前缀的Overlap相似度为1.

即, 公式(2)中的$si{m_O}(Prefix_r^i,Prefix_s^j) = 1$.此时, 公式(5)与公式(2)等价.

当一个候选对第ξ(ξ > 1)次出现时, 候选对前缀的Overlap相似度为ξ, 即$si{m_O}(Prefix_r^i,Prefix_s^j) = \xi $.使用公式(2), 当$\xi + \min (|Suffix_r^i|,|Suffix_s^j|) < \partial $时, 候选对才会被过滤掉; 而使用公式(5), 当$1 + \min (|Suffix_r^i|,|Suffix_s^j|) < \partial $时, 候选对就会被过滤掉.因为恒大于$1 + \min (|Suffix_r^i|,|Suffix_s^j|)$, 即:

$1 + \min (|Suffix_r^i|,|Suffix_s^j|) < \xi + \min (|Suffix_r^i|,|Suffix_s^j|) < \partial $

所以当ξ > 1, 公式(5)与公式(2)的正确性相同, 且有更强的过滤能力.证毕.

观察2.在对候选对进行后缀过滤过程中, 公式(6)与公式(3)的正确性相同, 且公式(6)具有更强的过滤能力.

证明:与位置过滤类似, 当第1次生成候选对时, 前缀中的Overlap相似度为1.

即, 公式(3)中的$si{m_O}(Prefix_r^i,Prefix_s^j) = 1$.此时, 公式(6)与公式(3)等价.

当一个候选对第ξ(ξ > 1)次出现时, 候选对前缀的Overlap相似度为ξ, 即$si{m_O}(Prefix_r^i,Prefix_s^j) = \xi $.使用公式(3), 当估算海明距H_c≥|r|+|s|-2·∂-(i+j-2·ξ)时, 候选对才会被过滤掉; 而使用公式(6), 当H_c≥|r|+|s|-2·∂-(i+j-2)时, 候选对就会被过滤掉.因为|r|+|s|-2·∂-(i+j-2·ξ)恒大于|r|+|s|-2·∂-(i+j-2), 即H_c≥|r|+|s|-2·∂-(i+j-2·ξ)≥|r|+|s|-2·∂-(i+j-2), 所以当ξ > 1时, 公式(6)与公式(3)的正确性相同, 且有更强的过滤能力.证毕.

3.2 Token批处理 3.2.1 事件驱动框架存在的问题

事件驱动框架主要执行过程是:对于前缀事件〈r, p_r, sp_r〉, 将记录r插入到p_r对应Token的倒排列表中, 扫描该倒排列表生成候选对, 随后再进行过滤和精确的相似度计算.事件驱动框架保证最后结果的正确性, 但是它存在的问题有:

(1)前缀事件堆的维护代价比较高;

(2)每次只处理记录的一个Token, 限制了临时结果堆顶候选对相似度sim_k的增长速度;

(3)存放候选对的哈希表太大, 需花费大量的建立和查找代价.

如果第k个最相似记录对的相似度值θ_k已知, 那么传统相似度连接算法(PPJoin或PPJoin+)的效率明显优于Topk-join算法.通过比较我们发现, PPJoin性能良好的原因在于:

(1) PPJoin将记录前缀中的Token全部批量的插入到索引表中;

(2) PPJoin在处理每一条记录时, 都利用一个较小的哈希表过滤重复的候选对;

(3) PPJoin生成的候选对数量明显少于Topk-join算法.

上述分析表明, 每次只处理一个Token是造成事件驱动框架效率低下的主要原因.为此, 我们考虑借鉴传统相似连接算法(PPJoin)中Token批处理的思想, 对事件驱动框架进行改进.具体来说, 当一个前缀事件到达之后, 我们不只处理一个Token, 而是同时处理多个Token, 即, 下一个前缀事件由〈r, p_r+1, sp_r〉转变为〈r, p_r+MultiLen, sp_r〉, 其中, MutiLen为不小于1的正整数.在Token批处理中, MultiLen的选取成为一个关键性的问题, 下面我们将对其进行详细的讨论与分析.

3.2.2 MultiLen的选取

如果第k个最相似记录对的相似度值θ_k已知, 根据前缀定理, MultiLen的值为

$MultiLen = \left\lfloor {\left| r \right| \cdot (1 - {\theta _k})} \right\rfloor + 1$

(7)

但是, θ_k在没有完成查询处理之前是无法获得的.在Topk-join算法执行过程中我们发现:当处理完上界值为1的前缀事件(即p_r=1, sp_r=1)后, 临时结果堆顶的候选对相似度值sim_k与θ_k相当接近.表 5给出了TREC数据集上执行Top200-1000查询时这两个相似度的值.基于上述观察, 我们考虑利用sim_k代替公式(7)中的θ_k求解MultiLen的值.

直接用sim_k代替θ_k, 带来的问题是每条记录的前缀都将会被扩大.以TREC数据集上top-1000查询为例, 如果某一条记录的长度为100, 那么它的前缀将由70扩大到75.前缀的扩张增加了过滤和哈希的代价, 同时也增加了候选对的数量, 所以需要对公式(7)中的长度|r|进行修正.

在分析数据特性时我们发现, 很多数据集在预处理之后记录的长度会集中在某一个区间.图 2给出了DBLP和TREC数据集的长度分布图.

可以看到, DBLP中记录的长度主要集中在[10, 23], TREC中记录的长度主要集中在[24, 46].如果我们选择频率最高的记录长度(即区间中的record number最大的记录长度, 记为L_m)来代替公式(7)中的|r|, 见公式(8), 那么会带来如下好处:

(1)会使长度小于L_m的前缀能够一次性执行完成, 临时结果堆顶相似度sim_k迭代加快;

(2)对于长记录的前缀也不会扩得太大.

$MultiLen = \left\lfloor {(1 - si{m_k}) \cdot {L_m}} \right\rfloor + 1$

(8)

同样以TREC数据集上Top-1000查询为例(L_m=25), 如果某一条记录的长度为100, 根据公式(8)计算的前缀长度为8, 小于该记录的实际前缀长度26.

虽然选取L_m具有上述优点, 但是仍然有以下两个问题需要解决.

(1)对于短记录的处理

对于长度远小于L_m的记录来说, 由于sim_k与θ_k非常接近, 如果仍然按照公式(8)计算MultiLen, 生成的前缀长度将会明显大于记录的实际前缀长度, 有的甚至超过记录本身.以DBLP数据集中长度最小的记录为例, 其中最小长度L_min=3, L_m=12, 当查询Top-20000时, θ_k=0.680, 根据公式(8)计算出来的MultiLen≥4 > L_min.因此, 有必要限制MultiLen值的大小.我们知道, 前缀事件〈r, p_r, sp_r〉中的p_r为前缀中下一个要处理Token的位置.如果临时结果堆顶的候选对相似度值为sim_k, 根据前缀定理, 所有未处理前缀长度的最大值为

$\left| r \right| - {p_r} - si{m_k} \cdot \left| r \right| + 1$

(9)

将公式(9)带入到公式(4)中, 对于每一条记录, 我们定义了MultiLen_max来限定MultiLen的取值, 如公式(10)所示.

$MultiLe{n_{max}} = \left\lfloor {(s{p_r} - si{m_k}) \cdot \left| r \right|} \right\rfloor + 1$

(10)

具体来说, 最终的Token批处理长度为MultiLen_ult=MIN (MultiLen, MultiLen_max).

仍以数据集DBLP为例, 利用公式(10), 在Top-20000中最短记录的MultiLen_ult为1而不再是4, 从而解决了短记录MultiLen过长的问题.

(2)对于长记录的处理

对于长度大于L_m的记录, 若每一次只处理MutiLen个Token, 则有时需要多次才能执行完成.以TREC数据集为例, 最长的记录为L_max=609.当k=400, θ_k=0.8时, 利用公式(8)计算的MultiLen值为10.根据前缀定理该记录的实际前缀长度为122, 如果每次只处理10个Token, 那么要13次才能完成处理, 从而增加了算法运行时间.为了减小长记录的计算次数, 我们对MultiLen进行扩展, 见公式(11).

$MultiLen = [(1 - si{m_k}) \cdot {L_m} + 1] \cdot coun{t^3}$

(11)

其中, count为该记录目前的处理批次.当第1次处理该记录的前缀事件时, 公式(11)得到的Multilen值与公式(8)相同.对于需要多批次处理的长记录, Multilen相对count的指数增长使得少量的批次就能完成该记录的处理, 从而提升算法性能.例如, 通过MultiLen扩展, TREC数据集中的最长记录第1次处理10个Token, 第2次处理80个Token, 最后一次处理剩余的32个Token, 因此只需通过3次就可执行完成.

3.2.3 Opt-join算法

通过在Topk-join中集成Token批处理技术和哈希优化策略, 新的Opt-join见算法3.Opt-join首先调用Bach-one(算法4)处理sp_r=1的所有前缀事件, 并为每条记录设定一个计数器, 计算记录执行的次数(算法4第6行); 随后, 使用公式(10)和公式(11)分别计算MultiLen和MultiLen_max, 将两者中最小值作为该记录批次的Token长度MultiLen_ult(第9行、第10行); 前缀事件的处理不再是只插入一个Token到倒排列表中, 而是插入MultiLen_ult个Token (第10行~第17行), 这样就加快了临时结果堆顶sim_k的迭代速度; 最后, 更新记录执行次数, 计算新前缀事件的上界值, 并将新前缀事件插入到堆中(第18行、第19行).

算法3. Opt-join(R, k).

输入:R为所有记录的集合; k表示要输出的相似对的个数;

输出:最相似的前k个记录对.

1. Initialize prefix event heap E and result heap T.

2. Bach-one(·);

3. WHILE E≠∅

4. 〈r, p_r, sp_r〉←E.pop(·);

5. sim_k=T[k].sim;

6. IF sp_r≤sim_k

7. break;

8.  ENDIF

9. Calculate Multilen and MultiLen_max;

10. MultiLen_ult←MIN (MultiLen, MultiLen_max);

11. FOR pos=p_r to p_r+MultiLen_ult

12. Generate candidate pairs (r, s);

13.  IF (r, s)∉H₀

14. Opt-hash(r, s);

15. H₀←H₀∪(r, s);

16. ENDIF

17.  ENDFOR

18. count_r←count_r+1;

19. E.push(r, p_r+MultiLen_ult, sp_r) and free H₀;

20.  ENDWHILE

在Opt-join算法中, 我们调用算法2(Opt-hash(r, s))来对候选对进行过滤(第14行).同时, 为了防止候选对重复计算, 在候选对生成之后, 增加了一个小哈希表H₀(第13行).在p_r到p_r+MultiLen_ult之间生成的所有候选对, 都要通过H₀过滤.MultiLen_ult个Token处理完成后, 释放小哈希表H₀(第19行).

算法4负责处理所有sp_r=1的前缀事件.前缀事件堆E的初始化阶段是将所有sp_r=1的前缀事件插入到堆中(详见第2节), 此时, 堆的大小为|R|.在对所有|R|个前缀事件处理地同时, 为每条记录初始化一个计数器(第6行), 记录当前记录处理的次数.

算法4. Bach-one(·).

1. FOR i=0 TO |R|

2. 〈r, p_r, sp_r〉←E.pop(·);

3. Generate candidate pairs (r, s) via index search;

4. Opt-hash(r, s);

5. Update the inverted index and T;

6. count_r←0; //Intialize the record execution times

7. E.push(r, p_r+1, sp_r);

8. ENDFOR

在Token批处理过程中, 由于sim_k与θ_rs之间的差值, 不可避免地增加了某些记录前缀的长度, 从而相应增加了生成的候选对数量.但是这一策略加快了sim_k的迭代速度, 提高了过滤技术的过滤能力(主要是Size过滤和位置过滤), 实际上是减小了需要验证的候选对的数量, 这在实验的结果中会有所体现.

4 实验评估

本节对Opt-join和Topk-join进行了实验比较.实验环境为:Dell T320, 1.9GHz Xeon (R) E5-2420六核处理器, 16G内存和1T磁盘; 操作系统为Ubuntu 12.04;程序设计语言为C++, 编译器为gcc-4.5.

为了能更好地看出哈希优化策略和Token批处理技术带来的性能提升, 实验中比较了如下3种算法.

(1) Topk-join:文献[3]中提出的Top-k相似连接算法;

(2)不使用Token批处理的Opt-join (OPT1):该算法在Topk-join算法的基础上, 只使用了哈希优化策略;

(3) Opt-join:该算法在事件驱动框架基础上, 结合了Token批处理技术, 且包含了OPT1的优化技术.

4.1 实验数据

与文献[2, 3]类似, 我们使用DBLP和TREC数据集来进行实验.DBLP包含了0.9M的记录(作者+标题); TREC选自于MEDLINE数据库, 我们从中抽取0.34M作为实验数据.预处理之后, 数据集的统计信息见表 6.与文献[3]类似, 我们使用Jaccard和Cosine相似度函数衡量记录对的相似度.

4.2 实验结果分析

下面我们将从哈希代价、候选对过滤能力、前缀事件堆大小、候选对数量以及运行时间5个方面对上述3种算法进行比较.受篇幅限制, 我们只列出了部分代表性实验结果.

(1)全局哈希表代价对比

哈希表的代价主要来自于哈希查找.图 3展示了在Topk-join算法和OPT1算法中, 哈希查找次数的对比.x轴表示k值, y轴表示哈希表查找的次数.可以发现:相对于Topk-join, OPT1的哈希查找次数明显减少.这是因为在Topk-join算法中, 所有的候选对都要进行哈希查找, 只有查找失败的候选对才进行过滤(位置过滤和后缀过滤); 而在OPT1算法中, 先做位置过滤和后缀过滤, 然后才进行哈希查找, 大量不符合条件的候选对已经被过滤掉了.所以, OPT1算法的哈希代价会远小于Topk-join.

(2)候选对过滤能力

图 4和图 5分别比较了Topk-join和Opt-join算法Size过滤和位置过滤的过滤能力, 其中, x轴表示k值, y轴表示被过滤掉的候选对个数.

可以发现:在Opt-join算法中, Size过滤和位置过滤的能力均得到了加强.这是由于在Opt-join算法中, Token批处理使得临时结果堆顶的候选对相似度sim_k迭代加快.由公式(1)可知, Size过滤能力主要依赖于sim_k.sim_k增长越快, Size过滤的过滤区间就越小, 其过滤能力就越强.所以, sim_k的快速增长, 使得Size过滤能力得到加强.

位置过滤能力增强的原因有:

1)公式(2)和公式(5)中, ∂值越大, 位置过滤的过滤能力越强.见表 2中, ∂值的大小依赖于sim_k.因此, sim_k的迭代加快导致阈值∂迅速增大, 从而使得位置过滤能力得到加强;

2)定理3中, 使用公式(5)代替公式(2)执行位置过滤后, 位置过滤能力得到加强.

由定理4可知:使用公式(6)代替公式(3)后, 后缀过滤能力将得到加强.但是, 由于大量不符合条件的候选对已被Size过滤和位置过滤剔除掉, 致使后缀过滤能力增加的不明显.以TREC数据集Top-500查询为例, 在Topk-join算法中, 后缀过滤剔除的不符合条件的候选对为25 662 651;而在Opt-join中, 剔除的不符合条件的候选对为26 868 795, 后缀过滤的能力只提高了4.7%左右.

(3)前缀事件个数

图 6比较了Topk-join和Opt-join中前缀事件的个数.在Topk-join中, 一个前缀事件只对应一个Token; 而使用了Token批处理技术后, 一个前缀事件对应于多个Token.在记录前缀不变的情况下, 使用Opt-join算法时前缀事件明显减少, 这就意味着前缀事件堆护所需的代价也相应降低.

从图 7中可以看出:TREC数据集中, 前缀事件减少了10倍左右; 而在DBLP数据集中, 前缀事件数目的减少不如TREC.主要原因是DBLP中记录长度太短, 记录的相似度太高, 导致计算出的MultiLen值太小.

(4)验证候选对数量对比

图 7给出了Topk-join和Opt-join算法中, 验证候选对的数量.验证候选对指通过过滤技术和哈希查找后, 需要精确计算相似度的候选对.精确计算是算法代价的主要来源之一, 验证候选对越少, 精确计算的代价就越低.通过图 7可以看出:Opt-join算法使用Token批处理技术后, 需要验证的候选对数量明显小于Topk-join算法(DBLP减少了约3倍, TREC约2倍).这是由于Token批处理技术使得sim_k的迭代加快(更快地达到实际的阈值), 从而增强了候选对过滤能力(如图 4和图 5所示), 使得需要精确计算相似度的候选对数量极大地减少.

(5)程序运行时间

图 8给出了Top-k join, OPT1和Opt-join算法程序运行时间的对比.为了方便比较, 我们定义加速比为Opt-join (OPT1)和Topk-join时间的比值.可以发现:OPT1算法明显优于Topk-join, 主要原因是Opt-join算法通过变更哈希查找和过滤操作的位置, 使得哈希表查找代价显著减小.Opt-join算法优于OPT1, 主要是Opt-join在OPT1的基础上, 又使用了Token批处理技术, 使其在候选对过滤能力、前缀事件个数、候选对数量上都优于OPT1(如实验1~实验4所示).如图 8(a)、图 8(c)和图 8(d)所示, OPT1比Topk-join算法的运行时间减少了20%左右.在图 8(b)中, OPT1的性能只提高了8%, 其原因是在相同k值下, Cosine相似函数对应的相似阈值高于Jaccard (例如在k=500时, Cosine相似函数下的阈值为0.96, Jaccard相似函数下的阈值为0.92), 所以使用Cosine相似函数时生成的候选对个数远小于Jaccard下的个数(k=500时, Cosine相似函数下的候选对个数为140万, Jaccard相似函数下的候选对个数为253万).候选对越少, Topk-join中哈希代价越低, OPT1性能提高的就越少.可以发现:随着k值增加, 生成的候选对变得越多, OPT1的优化也就越明显.

Opt-join在OPT1基础上增加了Token批处理, 与Topk-join相比, Opt-join显著地提高了算法的性能.如图 8(a)所示, Opt-join取得了1.28~1.46加速比.随着k的不断增加, 加速比有不断增大的趋势.在图 8(b)中, Opt-join的加速比是1.65~1.69, 这是由于相同k值下, Cosine相似函数对应阈值高于Jaccard下的阈值, 所以记录前缀长度小于Jaccard下相应的长度, 这就导致Token批处理的次数减小, 从而减少了程序运行时间.在TREC数据集下, Opt-join在Jaccard和Cosine相似度函数下的加速比分别为2.61~3.09和1.59~2.27, 如图 8(c)、图 8(d)所示.这是由于TREC数据集中的记录长度比较长, 当k相同时, Cosine相似函数下的sim_k值大于Jaccard相似函数下的值.由公式(7)可知:Cosine相似函数下, MultiLen的长度会小于Jaccard相似函数下相应的值.根据公式(11), 后续MultiLen的增长在Jaccard相似函数下的值会更大, 因此, 其批处理次数会减少, 相应的加速比较Cosine要更好.需要注意的是:在DBLP数据集中, 记录的长度较短, sim_k的值比较大, 导致计算出的MultiLen变化较小, 所以起决定作用的是前缀的长度.

总之, 在使用了两个优化技术之后, Opt-join可以取得1.28~3.09的加速比, 且随着k值的增加或数据集中记录长度的增长, 加速比有不断增大的趋势.

5 相关工作

相似连接算法在近几年已经获得广泛的关注.目前的相似连接算法可以归纳为两大类:基于阈值的相似连接和Top-k相似连接.

·基于阈值的相似连接算法已经获得广泛的研究^{[1, 2, 4-9, 10-23]}.文献[7]首先提出了前缀过滤算法; 文献[1]利用倒排索引和各种过滤技术, 对Cosine相似度下的相似连接算法进行优化; 文献[2]在前缀过滤的基础上提出了位置过滤和后缀过滤, 大大降低了需要验证的候选对的数量; 文献[11, 24]将相似连接算法应用与Map-Reduce中, 可以处理P级以上的大数据集;

· Top-k相似连接返回记录集中最相似的前k个记录对, 主要应用于相似度阈值未知的情况^{[3, 10, 25]}.文献[3]中首次使用基于事件驱动的框架来处理Top-k相似连接算法; 文献[10]使用编辑距(edit-distance)来计算Top-k的相似连接; 文献[25]使用Map-Reduce框架来支持Top-k相似连接算法.

6 结语

本文对Top-k相似连接算法进行了研究.在Topk-join算法的基础上, 提出了哈希优化策略和Token批处理技术, 并将这两个技术与前缀事件处理框架结合, 设计了新的Top-k相似连接算法Opt-join.

实验结果表明:Opt-join在哈希代价、候选对过滤能力、前缀事件堆大小、候选对数量以及运行时间等5个方面都优于Topk-join算法, 取得了1.28~3.09的加速比.随着k值的增加或数据集中记录长度的增长, 加速比有不断增大的趋势.