关键词: 字符串相似性查找, 阈值, top-k, 分割, 编辑距离

Abstract: The problem of string similarity search involves two aspects, threshold-based string similarity search and top-k string similarity search. At present, the methods of dealing with threshold-based string similarity search problem mostly are based on the filter-and-verification framework. Based on this framework, this paper proposes an algorithm called PBsearch. In the filtering step, it adds One-Off condition to filter a large number of invalid matches. And in the verification step, it uses a new method called MultiThreshold to greatly reduce the number of edit distance computation. To deal with top-k string similarity search problem, this paper puts forward two partition-based algorithms called Pb-topk and PbCount-topk. Pb-topk algorithm uses the increment of the difference strategy to reduce the number of strings to be processed. And PbCount-topk algorithm uses the partition of the number of matching strategy to further refine the size of the candidate set. Finally, the experimental results on three real data sets verify the efficiency of these proposed algorithms.

Key words: string similarity search, threshold, top-k, partition, edit distance