Name
Abstract | ||
|---|---|---|
This paper proposes an indexing technique for fast retrieval of similar subsequences using the time-warping distance. The time-warping distance is a more suitable similarity measure than the Euclidean distance in many applications where sequences may be of different lengths and/or different sampling rates. The proposed indexing technique employs a disk-based suffix tree as an index structure and uses lower-bound distance functions to filter out dissimilar subsequences without false dismissals. To make the index structure compact and hence accelerate the query processing, it converts sequences in the continuous domain into sequences in the discrete domain and stores only a subset of the suffixes whose first values are different from those of the immediately preceding suffixes. Extensive experiments with real and synthetic data sequences revealed that the proposed approach significantly outperforms the sequential scan and LB scan approaches and scales well in a large volume of sequence databases. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0306-4379(02)00102-3 | Inf. Syst. |
Keywords | Field | DocType |
similarity search,categorization,suffix tree,indexing,time warping distance,indexing technique,index structure,continuous domain,different sampling rate,index structure compact,sequence database,euclidean distance,sux tree,discrete domain,different length,time-warped subsequence,time-warping distance,lower-bound distance function,distance function,synthetic data,lower bound,indexation | Data mining,Similarity measure,Computer science,Search engine indexing,Artificial intelligence,Generalized suffix tree,Suffix tree,Nearest neighbor search,Sequence database,Pattern recognition,Euclidean distance,Full table scan,Database | Journal |
Volume | Issue | ISSN |
28 | 7 | Information Systems |
Citations | PageRank | References |
14 | 0.93 | 20 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sanghyun Park | 1 | 729 | 80.64 |
| Wesley W. Chu | 2 | 2311 | 789.42 |
| Jee-Hee Yoon | 3 | 49 | 8.70 |
| Jung-Im Won | 4 | 86 | 10.56 |