We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
SBASS: Segment based approach for subsequence searches in sequence databases.
- Authors
Sanghyun Park; Kim, S.-W.; Chu, W. W.
- Abstract
This paper investigates the subsequence searching problem tinder time warping in sequence databases. Time warping enables to find sequences with similar changing patterns even when they are of different lengths. Our work is motivated by the observation that subsequence searches slow down quadratically as the total length of data sequences increases. To resolve this problem, we propose the Segment-Based Approach for Subsequence Searching Technique (SBASS), which modifies the similarity measure from time warping to piece-wise time warping and limits the number of possible subsequences be compared with a query sequence. That is, the SBASS divides a data sequence X҆ and a query sequence q҆ into piece-wise segments and compares q҆ with only those subsequences which consist of n consecutive segments of X҆. Here, n is the number of segments in q҆. For efficient retrieval of similar subsequences, we extract feature vectors from all data segments exploiting their monotonically changing properties, and build a multi-dimensional index. Using this index, queries are processed with four steps: (1) index filtering, (2) feature filtering, (3) successor filtering, and (4) post-processing. The effectiveness of our approach is verified through experiments on synthetic data sets.
- Subjects
TIME-sharing computer systems; DATABASES; MULTIDIMENSIONAL databases; QUERYING (Computer science); PROGRAMMABLE sequence controllers; COMPUTER systems
- Publication
Computer Systems Science & Engineering, 2007, Vol 22, Issue 1/2, p37
- ISSN
0267-6192
- Publication type
Article