A New String Search Tree with Multiple Alignment
Sunghwan Kim, Kwanghwi Kim, Hwan-Gue Cho · 2012
String similarity search is a fundamental problem in computer science and can be applied to various fields of information processing. Construction of an efficient indexing structure is an important challenge to improve search performance. In this paper, we propose a new effective tree structure for string similarity search under Levenshtein distance. We present a bottom-up approach to construct the search tree, the internal nodes of which indicate a multiple-sequence alignment of its child leaf nodes, while a leaf node representing a string element. Defining an operation to merge strings and an algorithm for computing distance to merged strings, we present an efficient search strategy with our proposed tree structure. We also demonstrate the search performance with an experimental evaluation, and verify that our method outperforms the sequential search by at most a factor of 15 in terms of the search time.