Can I read Bed-tree: an All-purpose Index Structure for String Similarity Search Based on Edit Distance on EtoBox?

Bed-tree: an All-purpose Index Structure for String Similarity Search Based on Edit Distance by Zhenjie Zhang; Marios Hadjieleftheriou; Beng Chin Ooi; Divesh Srivastava is a scholarly article available to read on EtoBox.

What is Bed-tree: an All-purpose Index Structure for String Similarity Search Based on Edit Distance about?

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 B ed -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

Author

Zhenjie Zhang; Marios Hadjieleftheriou; Beng Chin Ooi; Divesh Srivastava

Publisher

ACM

Published

2010

Language

EN