关键词: 字符串相似连接, 双向过滤-验证机制, 过滤-验证框架

Abstract: A string similarity join finds similar string pairs from two sets of strings. It plays an important role in many real-world applications. Various algorithms have been proposed to address its efficiency issues. Partition-based filter-verification methods, such as Pass-Join, are promising, which quickly screens out possible similar string pairs（candidate set）by searching partitioned parts of a string in another string, in order of increasing length, and then performs similarity verification based on edit-distance. Motivated by the fact that the effect produced by filtering in the descending order of string length is better than in the ascending order, a novel bi-directional filtering-verification mechanism is proposed. At the filtering stage, it pipelines the results from length descending filtering to length ascending filtering to further reduce the size of the candidate set. At the verification stage, it makes use of the two pairs of matched substrings from the bi-directional filtering to partition the target string pairs into several short substring pairs to accelerate the verification process. Experimental results show that the proposed bi-directional filtering-verification algorithm outperforms the origin algorithm on real-world datasets.

Key words: string similarity joins, bi-directional filtering-verification mechanism, filter-verification framework