A Suffix Tree for Fast Similarity Searches of Time-Warped Sub-Sequences in Sequence Databases
Sanghyun Park, Wesley W. Chu, Jeehee Yoon, Chih‐Cheng Hsu · 2000
Several indexing techniques have been proposed to process similarity queries in sequence databases. Most of them focus on finding similar sequences of the same length using the Euclidean distance metric. However, in some applications where the elements of sequences may be sampled at different rates, the time warping distance is a more suitable similarity measure. In this paper, we propose an indexing technique based on a suffix tree for fast retrieval of similar sub-sequences under time warping. The search algorithm for a suffix tree is extended to provide similarity searches, and the concept of categorization is applied to reduce index size and to accelerate query processing. A greater reduction of index size is achieved using a sparse suffix tree and more speed-up is attained by the fast estimation of the time warping distances between non-stored suffixes and a query sequence. Our method guarantees no false dismissals since the actual time warping distances are always lower-bound in ...