Efficient Similarity Search in Very Large String Sets
Efficient Similarity Search in Very Large String Sets
复制标题
DOI：
10.1007/978-3-642-31235-9_18
复制
发表时间：
2012-06
期刊：
影响因子：
--
通讯作者：
D. Fenz;Dustin Lange;Astrid Rheinländer;Felix Naumann;U. Leser
中科院分区：
文献类型：
--
作者：
D. Fenz;Dustin Lange;Astrid Rheinländer;Felix Naumann;U. Leser
字符串相似性搜索是许多实际应用所必需的，例如拼写检查、数据清理、模糊关键字搜索或DNA序列比较。给定一个非常大的字符串集合和一个查询字符串，字符串相似性搜索问题是有效地找到字符串集合中与查询字符串相似的所有字符串。相似性是使用相似性（或距离）度量来定义的，例如编辑距离或汉明距离。在本文中，我们引入了状态集索引（SSI）作为这个搜索问题的有效解决方案。SSI是基于一个特里（前缀索引），被解释为一个不确定的有限自动机。SSI实现了一种新的状态标记策略，使索引具有很高的空间效率。此外，SSI的空间消耗可以优雅地与搜索时间进行交易。我们对来自社交网络的多达1.7亿个字符串的不同人名集进行了SSI评估，并将其与其他最先进的方法进行了比较。我们表明，在大多数情况下，SSI是显着快于其他工具，需要更少的索引空间。
String similarity search is required by many real-life applications, such as spell checking, data cleansing, fuzzy keyword search, or comparison of DNA sequences. Given a very large string set and a query string, the string similarity search problem is to efficiently find all strings in the string set that are similar to the query string. Similarity is defined using a similarity (or distance) measure, such as edit distance or Hamming distance. In this paper, we introduce the State Set Index (SSI) as an efficient solution for this search problem.SSI is based on a trie (prefix index) that is interpreted as a nondeterministic finite automaton. SSI implements a novel state labeling strategy making the index highly space-efficient. Furthermore, SSI’s space consumption can be gracefully traded against search time.We evaluated SSI on different sets of person names with up to 170 million strings from a social network and compared it to other state-of-the-art methods. We show that in the majority of cases, SSI is significantly faster than other tools and requires less index space.