Bed-tree: an all-purpose index structure for string similarity search based on edit distance
Bed-tree: an all-purpose index structure for string similarity search based on edit distance
复制标题
DOI：
10.1145/1807167.1807266
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
Zhenjie Zhang;Marios Hadjieleftheriou;B. Ooi;D. Srivastava
中科院分区：
文献类型：
--
作者：
Zhenjie Zhang;Marios Hadjieleftheriou;B. Ooi;D. Srivastava
字符串在计算机系统中无处不在，因此字符串处理吸引了不同领域的计算机科学家的广泛研究工作。字符串处理中最重要的问题之一是根据指定的相似性度量有效地评估两个字符串之间的相似性。字符串相似性搜索是信息检索、数据库清理、生物序列分析等领域的一个基本问题。虽然已经提出了大量字符串的相异性度量，但编辑距离是广泛应用中最流行的选择。现有的基于编辑距离的相似性搜索查询的索引技术，例如近似选择和连接查询，主要依赖于与倒排列表结构相结合的n-gram签名。这些技术仅针对特定查询类型而定制，其性能仍然不能令人满意，尤其是在内存限制严格或数据更新频繁的场景下。在本文中，我们提出了 Bed-tree，一种基于 B+ 树的索引结构，用于评估所有类型的编辑距离和归一化编辑距离的相似性查询。我们确定从字符串空间到整数空间的映射的必要属性，以支持这些查询的搜索和修剪。提出了三种转换来捕获字符串固有信息的不同方面，从而在树上的搜索过程中实现高效的修剪。与最先进的字符串相似性搜索方法相比，Bed-tree 是一个完整的解决方案，可以满足所有应用程序的要求，提供高可扩展性和快速响应时间。
Strings are ubiquitous in computer systems and hence string processing has attracted extensive research effort from computer scientists in diverse areas. One of the most important problems in string processing is to efficiently evaluate the similarity between two strings based on a specified similarity measure. String similarity search is a fundamental problem in information retrieval, database cleaning, biological sequence analysis, and more. While a large number of dissimilarity measures on strings have been proposed, edit distance is the most popular choice in a wide spectrum of applications. Existing indexing techniques for similarity search queries based on edit distance, e.g., approximate selection and join queries, rely mostly on n-gram signatures coupled with inverted list structures. These techniques are tailored for specific query types only, and their performance remains unsatisfactory especially in scenarios with strict memory constraints or frequent data updates. In this paper we propose the Bed-tree, a B+-tree based index structure for evaluating all types of similarity queries on edit distance and normalized edit distance. We identify the necessary properties of a mapping from the string space to the integer space for supporting searching and pruning for these queries. Three transformations are proposed that capture different aspects of information inherent in strings, enabling efficient pruning during the search process on the tree. Compared to state-of-the-art methods on string similarity search, the Bed-tree is a complete solution that meets the requirements of all applications, providing high scalability and fast response time.