Efficient top-k algorithms for approximate substring matching
Efficient top-k algorithms for approximate substring matching
复制标题
DOI：
10.1145/2463676.2465324
复制
发表时间：
2013-06
期刊：
影响因子：
--
通讯作者：
Younghoon Kim;Kyuseok Shim
中科院分区：
文献类型：
--
作者：
Younghoon Kim;Kyuseok Shim
有很多应用程序需要查询大型文本数据库来搜索相似的字符串或子字符串。传统的近似子字符串匹配要求用户指定相似度阈值。如果没有top-k近似子串匹配，当合适的阈值事先未知时，用户必须反复尝试不同的最大距离阈值。在本文中，我们首先提出了在一组数据字符串中寻找与给定查询字符串匹配的top-k近似子字符串的有效算法。为了减少昂贵的距离计算次数，所提出的算法利用我们的新颖滤波技术，利用可用的q-g和倒q-g索引。我们用真实的数据集进行大量的实验。实验结果证实了算法的有效性和可扩展性。
There is a wide range of applications that require to query a large database of texts to search for similar strings or substrings. Traditional approximate substring matching requests a user to specify a similarity threshold. Without top-k approximate substring matching, users have to try repeatedly different maximum distance threshold values when the proper threshold is unknown in advance. In our paper, we first propose the efficient algorithms for finding the top-k approximate substring matches with a given query string in a set of data strings. To reduce the number of expensive distance computations, the proposed algorithms utilize our novel filtering techniques which take advantages of q-grams and inverted q-gram indexes available. We conduct extensive experiments with real-life data sets. Our experimental results confirm the effectiveness and scalability of our proposed algorithms.