相似连接算法在数据清理、数据集成和重复网页检测等领域有着广泛的应用。相似度的度量方法有多种,包括Jaccard相似度,Cosine相似度,Dice相似度和Hamming距离等。本文中主要集中于字符串Jaccard相似度和Cosine相似度连接算法的研究。目前的相似连接算法有两种类型:基于相似度阈值的相似连接和Top-k相似连接。基于阈值的相似连接就是给定阈值θ,求出字符串集合中不小于θ的字符串对;Top-k相似连接就是阈值未知,需要求出字符串集合中最相似的前k个字符串对。Top-k连接算法非常适合于相似度阈值未知的应用场景,目前最为有效的Top-k相似连接算法是Xiao等人提出的Topk-join。但该算法存在问题主要包括:为了减少重复计算,算法执行过程中生成的每一个候选记录对都需要查找哈希表,从而导致哈希查找代价过大;每次前缀事件只处理记录的一个Token,使得临时结果集逼近真实结果的速度较慢,同时造成前缀事件和临时结果堆的维护代价过大。针对上述问题,本文提出了一种基于Token批处理的Top-k相似连接算法Opt-join。新算法将Token批处理技术集成在现有的事件驱动框架中,以降低前缀事件的处理代价;通过提高后缀过滤的maxdepth深度优化算法性能,并对maxdepth的选取给出了定性的分析;通过置换哈希查找与过滤操作的执行位置来降低哈希查找代价,并理论证明了该置换的正确性;实验结果表明,与Topk-join算法相比Opt-join取得了1.28-3.09倍的性能提升。实验数据还显示随着数据长度增加或k值增长,Opt-join的性能优势有不断增加的趋势。