关键词: 编辑距离, 相似性连接, 多次匹配, 数据清理, Pass-Join-K 算法

Abstract: Similarity join is the basic model of data cleaning in the database research and has attracted lots of attention from the database community. This paper studies the edit distance based similarity join, which finds similar strings from two large sets of strings whose edit distance is less than a given threshold, and proposes an improved Pass-Join algorithm, named Pass-Join-K. Pass-Join-K is efficient both for short strings and long strings. The main idea of Pass-Join-K is to divide the query string into more parts based on the partition strategy of Pass-Join, and filter the candidate string pairs more strictly by multi-match. The experimental results show that Pass-Join-K can decrease the candidate pairs, and run 2-5 times more quickly than the origin algorithm which outperforms state-of-the-art methods on real datasets.

Key words: edit distance, similarity join, multi-match, data cleaning, Pass-Join-K