相似连接是数据管理领域的一个热门话题,已在社会生产生活中得到广泛应用.然而,现有的相似连接方法并不能满足真实世界不断增长的客观需求.通过引入定义在多种数据类型上的满足操作符和每条数据的独立阈值,定义了一种相似连接——泛化双向相似连接.这种连接扩展了相似连接的应用范围.同时,还提出了两种高效的解决泛化双向相似连接问题的方法:子连接集算法和映射-过滤-验证算法.通过真实与合成数据集上的大量实验,得出了所提方法的正确性和有效性.
Similarity join is one of the hottest topics in the field of data management, and it has been widely applied in many fields. However, existing similarity join methods cannot meet the increasing demands in the real world. This paper define generalized bisimilarity join as a new similarity join to expend the applications of the similarity join research by introducing the satisfaction operator on various data types with individual thresholds. Two efficient methods, SJS(sub-join set) and MFV(mapping-filtering-verification), are proposed to solve this problem. A large amount of experiments conducted on both real-world and synthetic datasets demonstrate the correctness and the effectiveness of the proposed methods.
相似连接旨在从两个或一个给定的数据集中找出满足预定连接条件的所有数据对.作为数据库应用中的一个重要操作, 相似连接受到学术界和工业界的普遍关注, 并在重复检测[
数据库研究者已针对不同类型的数据进行了大量的相似连接研究工作, 如关系数据[
场景1(交友):假设有两位女士{Alice, Carol}和两位男士{Bob, Dave}希望结交异性.见
交友信息
Dating information
(a)男士集合 | ||||||
姓名 | 年龄 | 身高 | 教育 | 有房 | 婚姻 | 阈值 |
Bob | 26 |
174 |
D |
N |
S |
100% |
Dave | 27 |
175 |
B |
Y |
S |
80% |
… | … | … | … | … | … | … |
(b)女士集合 | ||||||
姓名 | 年龄 | 身高 | 教育 | 有房 | 婚姻 | 阈值 |
Alice | 23 |
166 |
D |
N |
S |
100% |
Carol | 24 |
167 |
B |
N |
S |
80% |
… | … | … | … | … | … | … |
场景2(求职招聘):求职和招聘是工作市场中的一个重要话题.招聘者会提供薪水、假期和工作地点的事实以及对于应聘者的专业技能和工作经验等的期望.同时, 求职者会对应地提供他们对于薪水、假期、工作地点的期望以及他们的专业技能和工作经验的事实.与交友场景类似, 不同的求职者和招聘者会有着不同的对于匹配程度的最低标准.
此外, 还存在房屋租赁等一系列类似应用场景及问题.显然, 现有的相似连接方法不能直接用来解决这些问题.其主要原因在于:
(1) 现有的相似连接方法通常仅考虑一种数据类型, 如字符串或向量, 并根据这种数据类型的特点提出特殊的处理方法以提高连接效率.然而, 在上述问题中存在着多种数据类型, 如有房属性中的布尔类型数据, 年龄、身高属性中的数值范围和数值类型数据;
(2) 现有的相似连接方法采用全局阈值, 但是在场景1中, 采用全局阈值不能得到{(Carol, Dave)}这样的理想连接结果.当全局阈值被设置为100%时, 连接结果为空集, 而当全局阈值被设置为60%时, 连接结果为两个集合的笛卡尔积.显然, 这两个结果都与理想结果存在差距;
(3) 现有的所有相似连接方法只在同一个属性维度上考虑了两个比较对象的相等关系或者某种偏序关系.但是在上述场景中, 我们需要在事实类属性和对应的期望类属性上考虑上述关系.同时, 更复杂的关系(如“包含”)也可能被考虑.
我们认为, 上述问题存在以下3个挑战:(1)每个比较对象都存在自己独立的匹配标准, 虽然这类标准可以通过阈值进行刻画, 但是无法采用当前相似连接查询处理方法中普遍使用的全局阈值; (2)上述问题涉及数值、数值范围、枚举、布尔、字符串等多种类型的数据, 这使得对象的比较方式更加多样化; (3)每个比较对象都有事实类属性和期望类属性, 具体比较时, 事实属性和期望属性的交叉匹配将取代在同一属性上的简单比较, 使得比较方式更为复杂.
针对以上挑战, 本文提出泛化双向相似连接的概念及相关查询处理算法, 能够较好地解决上述问题.本文的主要贡献如下.
(1) 提出了一种新的相似连接概念——泛化双向相似连接.这种连接支持泛化数据类型(包括数值、数值范围、枚举、布尔、字符串等)的事实属性与对应期望属性的交叉比较; 通过为每个比较对象设置独立阈值, 使得连接结果更加符合用户客观需求;
(2) 针对泛化双向相似连接查询处理问题, 提出子连接集算法和映射-过滤-验证算法.对于映射-过滤-验证算法, 还提出了3种映射方法.其中, 启发式映射方法在性能上优于单射和等步长映射, 能进一步提高算法效率;
(3) 在真实和合成数据集上的实验结果表明, 本文所提的两种算法相对于基准算法有效提高了运算效率.同时, 实验结果显示了为用户设置独立阈值得到的连接结果要优于仅通过全局阈值获得的连接结果.
本文第1节介绍相关工作.第2节给出泛化双向相似连接的形式化定义.第3节提出泛化双向相似连接查询处理算法并分析其时间复杂度, 同时论述算法的正确性.第4节给出两种改进的映射方法.第5节对实验结果进行展示和分析.第6节总结全文.
与本文最相似的工作是相似连接.数据库研究者已针对不同类型的数据进行了大量的相似连接的研究工作, 如关系数据[
在以上这些相似连接工作中, 字符串相似连接(SSJ)是最具典型性的一个代表, 也是近些年数据库领域非常热门的话题.它被用于查找两个字符串集合中所有相似的字符串.现有的SSJ研究成果可以分为如下3类:第1类是基于索引的方法, 它们使用了针对字符串的不同的索引结构, 如Trie树[
然而, 上述方法都不能直接应用于泛化双向相似连接.原因可以归纳为如下3点:首先, 大多数已有的研究工作集中于考虑字符串, 而很少考虑同时包含字符串、数值、枚举等多种数据类型的泛化数据; 其次, 现有的字符串相似连接方法仅仅考虑点对点的比较, 没有处理数值范围的能力, 同时也不支持交叉比较; 最后, 现有的字符串相似连接方法均采用全局统一的阈值, 没有将独立阈值纳入研究范围.
本节首先定义一种新的操作符, 在此基础上给出泛化双向相似连接的形式化定义.论文用到的符号及其含义见
符号及其含义
Symbols and meanings
符号 | 含义 |
阈值 | |
数据集 | |
数据集中的一条记录 | |
∝ | “满足”操作符 |
⋈ | 泛化双向相似连接运算 |
记录 |
|
记录 |
|
记录 |
“满足”(∝)操作符定义在事实和对应的期望上.对于不同类型的数据, “∝”的判定标准不尽相同.举例来说, 如果事实
其中,
(1)
(2)
如
泛化双向相似连接示意图,
An illustration of bisimilarity join,
类似地, 可计算出其他
根据上述计算结果, 因为
本节首先给出解决泛化双向相似连接的嵌套循环(nested loop)算法, 接着提出两种采取不同策略的更高效的算法:一种是基于分治思想的子连接集(sub join set)算法, 其针对不同的属性采取不同的处理方式; 另一种是基于归一化思想的映射-过滤-验证(mapping filtering verification)算法, 其将泛化数据类型统一为符号表示进行处理.最后, 我们论证了3种算法的正确性, 并且比较了它们的优缺点与适用场景.
如前所述, 现有的专用于相似连接查询处理的算法都不能直接用来解决泛化双向相似连接问题.注意到, 朴素的嵌套循环算法是可以应用于任何连接问题的.于是, 本节介绍如何将嵌套循环算法应用于泛化双向相似连接, 并将其作为后继方法的比较基准.
嵌套循环算法的思路简单而有效, 它比较
假定计算
提出一种基于分治策略的算法——子连接集算法, 它将泛化双向相似连接分解成一系列的子连接问题来解决.每个子连接在单一属性上根据事实和期望对两个数据集合进行连接, 对于每一个单一属性, 都会建立适合其数据类型的索引结构来进行连接操作.通过合并每一个子连接的结果, 我们可以得到最终的泛化双向相似连接的结果.具体算法见算法1.
输入:
输出:
1.
/*为数据集合
2. FOR ALL
3.
4. FOR ALL
5.
/*利用索引计算每一个子连接并合并*/
6.
7. FOR ALL
8.
9.
10. FOR ALL
11.
/*通过合并后的子连接的结果验证每一对数据*/
12. FOR ALL
13. FOR ALL
14. IF
15.
16. RETURN
首先, 我们为数据集
然后, 我们对
输入:
输出:
1.
2. FOR ALL
3.
4.
5. RETURN
我们使用比特矩阵
接下来, 我们用相似的方式, 对于数据集
最终, 我们通过分析两个矩阵的值来验证每一个可能的结果对.对于结果对(
用场景1中的例子来说明子连接集算法:首先, 对于男士集合和女士集合的所有属性分别建立高效的索引, 具体来说, 对年龄和身高属性建立了B+树索引, 对教育和婚姻属性建立了倒排索引, 对有房属性建立了位图索引; 接下来, 在每个属性上进行子连接操作, 以女士集合的教育属性为例,
子连接集算法示例
An example of the SJS algorithm
本节提出另一种专门解决泛化双向相似连接问题的算法, 它包含映射、过滤和验证这3个步骤, 即映射-过滤-验证算法.首先, 在映射阶段, 所有记录的数据被映射到一个全局的符号集上; 然后, 过滤步骤排除掉不符合条件的数据对; 最后, 通过验证, 得到最终的结果集.
输入:
输出:
1.
/*映射步骤, 将数据映射为全局符号*/
2.
/*过滤步骤:预处理阶段——在
3.
4.
/*过滤步骤:在映射后产生的符号记录上进行双向过滤获得候选集合*/
5. FOR ALL
6. FOR ALL
7. FOR ALL (
8.
9. FOR ALL (
10. FOR ALL
11. IF (
12.
13. BREAK
/*验证阶段:对最终候选结果集执行双向验证获得最后的匹配结果*/
14. FOR ALL (
15. IF
16.
17. RETURN
算法3详细描述了3个具体步骤.
(1) 映射阶段
首先将数据集中每条记录的每个属性的数据映射到全局的符号上, 得到符号字典, 并在映射结束后, 通过统计和排序得到一个全局的按照出现次数递增排序的符号顺序
(2) 过滤阶段
首先, 对于
证明:若{
这与
之后, 过滤步骤将依据过滤原则生成候选结果对(步骤5~步骤13).具体地, 算法先枚举
(3) 验证阶段
将检验最终候选结果集
例如, 针对
单射规则和频率统计
Injective mapping rule
属性(值) | 映射符号 | 频率(事实属性中) |
年龄(20, 21, …, 27) | A, B, C, …, H | 0, 0, 0, 1, 1, 0, 1, 1 |
身高(165, 166, …, 174, 175) | I, J, K, …, S | 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1 |
教育(B, M, D) | T, U, V | 2, 0, 2 |
有房(Y, N) | W, X | 1, 3 |
婚姻(S) | Y | 4 |
单射规则和频率统计
Injective mapping result
(a)男士集合 | ||
姓名 | 映射结果 | 排序后结果 |
Bob | GRVXY |
GRVXY |
Dave | HSTWY |
HSWTY |
(b)女士集合 | ||
姓名 | 映射结果 | 排序后结果 |
Alice | DJVXY |
DJVXY |
Carol | EKTXY |
EKTXY |
应用单射后的索引结构
Index structure for injective mapping
在过滤阶段, 首先, 只有(Dave, Carol)被选入初始候选集合
与嵌套循环算法相比, 映射-过滤-验证算法通过提前过滤掉不可能的匹配对, 避免了记录之间不必要的相似性比较, 从而有效提高了泛化双向相似连接查询处理的效率.在上例中, 验证阶段前有75%的数据对被过滤掉, 这明显提高了查询处理效率.
本节提出的3个算法都是正确的.这里的正确性指不产生错误结果且不漏掉正确结果.嵌套循环算法通过遍历所有数据对, 来得到满足相似度阈值的全部结果.采用该方式, 嵌套循环方法不会引入错误结果, 也不会漏掉正确结果.子连接集算法同样遍历所有的数据对, 但是用一种比嵌套循环算法更高效的方式验证每一个结果对, 因此它也是正确的.对于映射-过滤-验证算法而言, 过滤步骤对一部分错误数据对提前进行剪枝操作, 而验证阶段则精炼最终候选结果集, 剔除剩余的错误数据对.同时, 因为在过滤过程中正确结果都会被保留(根据定理1), 所以不会产生正确结果的遗漏.综上所述, 本文提出的嵌套循环算法、子连接集算法和映射-过滤-验证算法都具有正确性.
嵌套循环算法相比于子连接集算法和映射-过滤-验证算法, 由于没有使用索引结构来加速, 在算法的时间效率上一定逊于后两者.不过, 索引结构本身是有空间开销的, 因此在空间限制极为严格的场景中, 嵌套循环算法还是有其意义的.子连接集算法和映射-过滤-验证算法采用了不同策略来解决我们的泛化双向相似连接问题:子连接集算法采用分治的思想, 对不同的属性建立不同类型的有针对性的索引结构, 分开处理每个属性; 映射-过滤-验证算法采用了归一化的思想, 将不同类型的属性值都统一映射成符号记录, 并建立一个包含所有属性的倒排索引, 可以同时处理所有属性.因此:当属性数较少时, 由于索引结构更有针对性, 子连接集算法将具有一定优势; 而当属性较多时, 受益于可以同时处理所有属性, 映射-过滤-验证算法会有更强的过滤能力, 从而更加高效.
本节提出两种新的映射方法, 以优化映射-过滤-验证算法中的映射阶段.同时, 对这些映射方法的优缺点进行分析比较.
在上一节中, 映射阶段统一采用单射方法.然而我们认为, 不同数据类型有各自的特性, 比如数值类型的属性就要比布尔类型的属性取值范围大.因此, 针对不同的数据类型, 我们可以考虑采用不同的映射策略, 以适应其特点, 并进一步提高索引结构的效率.下面, 我们将分析针对数值类型的映射策略.
前述单射方法在处理数值类型的属性时, 严格准确地将每个不同数值映射到一个唯一符号.但是, 如
等步长映射方法的基本思想是, 通过固定的步长来均匀分割数值范围数据.
等步长映射规则
Homogeneous mapping rule
属性(值) | 映射符号 | 频率(事实属性中) |
年龄(20~23) | A | 1 |
年龄(24~27) | B | 3 |
身高(165~169) | C | 2 |
身高(170~174) | D | 1 |
身高(175~180) | E | 1 |
教育(B, M, D) | H, I, J | 2, 0, 2 |
有房(Y, N) | W, X | 1, 3 |
婚姻(S) | Y | 4 |
等步长映射方法结果
Homogeneous mapping result
(a)男士集合 | ||
姓名 | 映射结果 | 排序后结果 |
Bob | BDJXY |
DJXBY |
Dave | BEIWY |
IEWBY |
(b)女士集合 | ||
姓名 | 映射结果 | 排序后结果 |
Alice | ACJXY |
ACJXY |
Carol | BCHXY |
CHBXY |
应用等步长映射后的索引结构
Index structure for homogeneous mapping
然而, 等步长映射方法的剪枝能力较单射的差.对
总体来说, 等步长映射方法通过将多个值映射到同样的符号, 减小了索引结构的规模和建立索引结构的时间开销.但是, 这会降低全局符号对于原始记录属性数据的区分性, 进而导致映射-过滤-验证算法在过滤阶段剪枝能力的下降.
基于前述讨论易知, 好的映射方法需要满足以下两个优化目标.
(1) 最小化映射后产生的符号记录数量;
(2) 最大化索引结构的剪枝效果(即, 最小化在过滤步骤后最终候选结果集合的大小).
事实上, 上述两个目标之间存在不一致性:一方面, 如果希望产生的符号记录最少, 那么通过将一个属性上的所有值都映射到同一个符号, 可以使得映射后产生的符号记录的数量与原始数据中记录的数量保持一致, 然而这样做, 过滤阶段将失去剪枝能力, 并导致最终候选结果集中的数据对与采用嵌套循环算法需要比较的数据对完全相同; 另一方面, 若要最大化索引结构的剪枝效果, 则应采用单射方法, 以使索引结构对于符号的区分性最强, 但这样会产生最大规模的符号记录集.
针对上述情况, 本文提出一种启发式映射方法的折衷方案, 尝试获得近似最优的映射方法.
(1)
(2)
(3)
在本节中, 集合
根据定义2, 一般情况下, 生成的符号记录的数量随着
通过上述分析, 可以得到如下结论:
接下来考虑索引结构的剪枝效果和划分
令
假设划分
于是, 上述最终优化目标可形式化表示为
其中, |
在上述例子中, |
本文称通过优化目标(1)获得的映射方法为启发式映射方法, 并将这种映射方法采用的划分
为了获得能达到优化目标的划分
针对枚举方法的不足, 本节提出了动态规划的方法来获得最优划分
得到上述最优子结构后, 就可以采用动态规划的方法获得最优划分, 对应的时间复杂度为
启发式映射规则
Heuristic mapping rules
属性(值) | 映射符号 | 频率(事实属性中) |
年龄(20~22) | A | 0 |
年龄(23~23) | B | 1 |
年龄(24~27) | C | 3 |
身高(165~167) | D | 2 |
身高(168~170) | E | 0 |
身高(171~173) | F | 0 |
身高(174~180) | G | 2 |
教育(B, M, D) | H, I, J | 2, 0, 2 |
有房(Y, N) | W, X | 1, 3 |
婚姻(S) | Y | 4 |
启发式映射结果
Heuristic mapping results.
(a)男士集合 | ||
姓名 | 映射结果 | 排序后结果 |
Bob | CGJXY |
GJCXY |
Dave | CGHWY |
WGHCY |
(b)女士集合 | ||
姓名 | 映射结果 | 排序后结果 |
Alice | BDJXY |
BDJXY |
Carol | CDHXY |
DHCXY |
总的来说, 基于动态规划生成最优划分的启发式映射方法兼顾了映射后尽量少的生成符号记录和过滤阶段较好的剪枝效率.通过上述分析, 可以得到如下结论:启发式映射方法优于等步长映射方法和单射映射方法.事实上, 它是根据第4.2.1节提出的优化目标得到的一类最优的映射方法.下一节的实验结果也展示了启发式映射方法比其他两种映射方法有着很大的优势.
采用Java语言实现了本文提出的算法, JDK为1.8.0.实验机器的配置为Xeon E5-2650 2.00GHz CPU, 256GB内存, 操作系统为Windows Server 2008 64位.
实验中采用了真实数据集DATING; 同时, 依据DATING中的数据分布规律生成了合成数据集L-DATING.
http://www.eharmony.com/)上爬取的, 并进行了去除隐私和归一化等操作.每条记录包括8个事实属性和8个对应的期望属性, 它们分别是居住城市、收入、子女和在
● L-DATING是合成数据集, 包括1 500 000条记录(男士和女士的信息各750 000条).每条记录里包含12个事实属性和12个期望属性.除了DATING原有的属性外, L-DATING还通过重复年龄、身高、教育和婚姻增加了4个额外的虚拟属性.L-DATING中的数据是根据DATING中对应属性上所有数据值的分布情况生成的.
在进行实验之前, 我们先对数据集进行了分析.
属性数据分布
Data distribution of attributes
因此, 如果我们使用等步长的映射方法, 有些符号会对应非常长的倒排列表.与此同时, 有些符号所对应的倒排列表又会很短.这种情况会严重影响倒排索引的效率.与此相对的是, 启发式映射方法可以利用属性的分布特征来确定划分方式.举例来说, 对于年龄属性, 启发式映射方法会将18~50区间内的值进行细粒度划分, 而对于区间外的值会采取粗粒度的划分.这种启发式映射方法使得各个符号所对应的倒排列表的长度相对平均, 从而提高倒排索引的效率.
本节通过实验分析比较MFV算法映射阶段的3种可选映射方法.为方便叙述, 用MFV-I, MFV-O和MFV-R分别代表采用单射的映射-过滤-验证算法、采用等步长映射的映射-过滤-验证算法和采用启发式映射的MFV算法.
生成记录数和候选集大小比较
Records and candidate pairs comparison
(1)
(2)
如
DATING数据集时间开销对比
Time cost comparison on DATING
以上实验结果表明:SJS算法和3个MFV算法在运行时间上都显著优于嵌套循环(NL)算法.这表明我们提出的用于解决泛化双向相似连接的算法都是非常有效的.在3种MFV算法中, MFV-R又表现最好, 这个结果显示了优化过的启发式映射方法比单射和等步长映射方法具有更好的效果.
直觉上说, 独立阈值更能体现用户的个性化需求, 例如, 能更加准确地描述一个人挑剔的个性或者其相对包容的个性.本节尝试通过客观实验来分析验证设置独立阈值的必要性.
全局阈值和独立阈值结果比较
Unified threshold vs. individual thresholds
从结果集规模上看, 这两个结果集的区别很小, 独立阈值似乎可以被全局阈值所取代.值得注意的是, 两个结果集中仅有46 532对结果是相同的, 这个数量还不到全部结果集规模的1/4.这表明采用两种不同的阈值设定方法会产生多达150 000对不同的结果.也就是说, 采用全局阈值得到的结果集与采用独立阈值得到的结果集存在相当大的差异.
因此, 为了满足真实世界的用户需求, 简单地采用全局阈值代替独立阈值是不合适的.这也进一步验证了本文的观点:在相似连接问题中, 为了满足不同用户的不同偏好, 采用根据用户个人情况制定出的独立阈值是值得尝试的.
由于真实数据集的规模有限, 所以我们采用合成数据进行实验以评价所提算法在较大规模数据集上的可扩展性.在合成数据集上的实验结果与在真实数据集上的实验结果有着相似的性质.
合成数据集时间消耗
Time cost comparison on L-DATING
合成数据集上MFV算法的生成记录数和候选集大小比较
Records and candidate pairs comparison on L-DATING
本文提出一种新的相似连接——泛化双向相似连接.它是对现有的大量相似连接工作的扩展, 适用于更加广泛的应用场景, 比如交友和求职招聘.同时提出了子连接集算法和映射-过滤-验证(MFV)算法来处理泛化双向相似连接查询, 并对于MFV算法提出了等步长映射方法和启发式映射方法, 以进一步提高算法效率.在真实和合成数据集上的大量实验结果, 表明了论文所提算法的正确性和有效性.此外, 对实验结果的深入比较分析显示, 采用用户独立阈值比采用全局统一阈值更符合用户需求.这也证明了在泛化双向相似连接中考虑独立阈值的必要性.今后将继续改进算法, 同时提高算法的可扩展性.
Xiao C, Wang W, Lin XM, Yu JX, Wang GR. Efficient similarity joins for near-duplicate detection. ACM Trans. on Database Systems (TODS), 2011, 36(3).[doi:10.1145/2000824.2000825]
Papapetrou P, Athitsos V, Kollios G, Gunopulos D. Reference-Based alignment in large sequence databases. Proc. of the VLDB Endowment, 2009, 2(1):205-216.[doi:10.14778/1687627.1687651]
Li YN, Patel JM, Terrell A. Wham:A high-throughput sequence alignment method. ACM Trans. on Database Systems (TODS), 2012, 37(4):28.[doi:10.1145/2389241.2389247]
10.1109/ICDE.2006.9]]]>
Liu XL, Wang HZ, Li JZ, Gao H. Similarity join algorithm based on entity. Ruan Jian Xue Bao/Journal of Software, 2015, 26(6):1421-1437(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4610.htm[doi:10.13328/j.cnki.jos.004610]
刘雪莉, 王宏志, 李建中, 高宏.基于实体的相似性连接算法.软件学报, 2015, 26(6):1421-1437. http://www.jos.org.cn/1000-9825/4610.htm[doi:10.13328/j.cnki.jos.004610]
Arasu A, Ganti V, Kaushik R. Efficient exact set-similarity joins. In:Proc. of the 32nd Int'l Conf. on Very Large Data Bases. 2006. 918-929.
10.1145/1807167.1807266]]]>
10.1109/ICDE.2012.91]]]>
Wang JN, Feng JH, Li GL. Trie-Join:Efficient trie-based string similarity joins with edit-distance constraints. Proc. of the VLDB Endowment, 2010, 3(1-2):1219-1230.
Li GL, Deng D, Wang JN, Feng JH. Pass-Join:A partition-based method for similarity joins. Proc. of the VLDB Endowment, 2011, 5(3):253-264.
Li R, Ju L, Peng Z, Yu ZW, Wang CK. Batch text similarity search with MapReduce. In:Proc. of the 13th Asia-Pacific Web Conf. Beijing, 2011. 412-423.
Lu W, Du XY, Hadjieleftheriou MM, Ooi BC. Efficiently supporting edit distance based string similarity search using B+-trees. IEEE Trans. on Knowledge and Data Engineering, 2014, 26(12):2983-2996.[doi:10.1109/TKDE.2014.2309131]
10.1109/ICDE.2015.7113311]]]>
10.1109/ICDE.2011.5767865]]]>
Wang W, Qin JB, Xiao C, Lin XM, Shen HT. VChunkJoin:An efficient algorithm for edit similarity joins. IEEE Trans. on Knowledge and Data Engineering, 2013, 25(8):1916-1929.[doi:10.1109/TKDE.2012.79]
10.1145/1807167.1807296]]]>
10.1145/2588555.2593675]]]>
Rong CT, Lu W, Wang XL, Du XY, Chen YG, Tung AKH. Efficient and scalable processing of string similarity join. IEEE Trans. on Knowledge and Data Engineering, 2013, 25(10):2217-2230.[doi:10.1109/TKDE.2012.195]
10.1109/ICDE.2014.6816663]]]>
Brualdi RA. Introductory Combinatorics. 5th ed., Pearson Education, 2009.