文档介绍：东华大学学位论文版权使用授权书
学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学校保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅或借阅。本人授权东华大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
保密□,在年解密后适用本版权书。
本学位论文属于
不保密□。
学位论文作者签名: 指导教师签名:
日期: 年月日日期: 年月日
Top-k 字符串相似连接算法性能优化研究
摘要
相似连接算法在数据清理、数据集成和重复网页检测等领域有着广泛的应用。相似度的度量方法有多种,包括 ard 相似度,Cosine 相似度,Dice 相似度和 Hamming 距离等。本文中主要集中于字符串 ard 相似度和 Cosine 相似度连接算法的研究。
目前的相似连接算法有两种类型:基于相似度阈值的相似连接和 Top-k 相似连接。基于阈值的相似连接就是给定阈值θ,求出字符串集合中不小于θ的字符串对;Top-k 相似连接就是阈值未知,需要求出字符串集合中最相似的前 k 个字符串对。
Top-k 连接算法非常适合于相似度阈值未知的应用场景,目前最为有效的 Top-k 相似连接算法是 Xiao 等人提出的 Topk-join。但该算法存在问题主要包括:为了减少重复计算,算法执行过程中生成的每一个候选记录对都需要查找哈希表,从而导致哈希查找代价过大;每次前缀事件只处理记录的一个 Token,使得临时结果集逼近真实结果的速度较慢,同时造成前缀事件和临时结果堆的维护代价过大。
针对上述问题,本文提出了一种基于 Token 批处理的 Top-k 相似连接算法 Opt-join。新算法将 Token 批处理技术集成在现有的事件驱动框架中,以降低前缀事件的处理代价; 通过提高后缀过滤的
I
maxdepth 深度优化算法性能,并对 maxdepth 的选取给出了定性的分
析;通过置换哈希查找与过滤操作的执行位置来降低哈希查找代价, 并理论证明了该置换的正确性;
实验结果表明,与 Topk-join 算法相比 Opt-join 取得了 - 倍的性能提升。实验数据还显示随着数据长度增加或 k 值增长,Opt-join 的性能优势有不断增加的趋势。
关键字:Top-k 相似连接;事件驱动框架;Token 批处理;哈希查找优化
II
OPTIMIZING TOP-K STRING SIMILARITY JOIN ALGORITHM
ABSTRACT
Similarity join is widely used in data cleaning, data integration and the detection of near duplicate webpages. There are many methods to measure the similarity, including ard, Cosine, Dice and Hamming. In this paper, we mainly focus on the research of the similarity join between the ard and Cosine.
Existing similarity join algorithms fall into two categories: the threshold-based similarity join and the Top-k similarity join. The threshold-based similarity join is that it gives a threshold
θ and returns pairs of string whose threshold is not less than θ; The Top-k similarity join is that
its threshold is unknown and we need to find the most k’s similar pairs of string form the collection.
Top-k similarity join is suitable for applications in which the threshold is unknown in advance. The most efficient Top-k similarity join algorithm is Topk-join, which is proposed by Xiao et al. But t