GFilter: A General Gram Filter for String Similarity Search

作者：Hu Haoji^*; Zheng Kai; Wang Xiaoling; Zhou Aoying

来源：IEEE Transactions on Knowledge and Data Engineering, 2015, 27(4): 1005-1018.

DOI：10.1109/TKDE.2014.2349914

• Data integration
• similarity search
• gram-based framework

Numerous applications such as data integration, protein detection, and article copy detection share a similar core problem: given a string as the query, how to efficiently find all the similar answers from a large scale string collection. Many existing methods adopt a prefix-filter-based framework to solve this problem, and a number of recent works aim to use advanced filters to improve the overall search performance. In this paper, we propose a gram-based framework to achieve near maximum filter performance. The main idea is to judiciously choose the high-quality grams as the prefix of query according to their estimated ability to filter candidates. As this selection process is proved to be NP-hard problem, we give a cost model to measure the filter ability of grams and develop efficient heuristic algorithms to find high-quality grams. Extensive experiments on real datasets demonstrate the superiority of the proposed framework in comparison with the state-of-art approaches.

• 单位
  华东师范大学