Bed-tree
Authors:
Open Access
- 6 June 2010
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 915-926
Abstract
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.Keywords
This publication has 17 references indexed in Scilit:
- Space-Constrained Gram-Based Indexing for Efficient Approximate String Search2009
- Fast Indexes and Algorithms for Set Similarity Selection Queries2008
- Efficient Merging and Filtering Algorithms for Approximate String Searches2008
- Low distortion embeddings for edit distanceJournal of the ACM, 2007
- The string edit distance matching problem with movesACM Transactions on Algorithms, 2007
- Efficient set joins on similarity predicates2004
- Robust and efficient fuzzy match for online data cleaning2003
- A faster algorithm computing string edit distancesJournal of Computer and System Sciences, 1980
- Ubiquitous B-TreeACM Computing Surveys, 1979
- The String-to-String Correction ProblemJournal of the ACM, 1974