Efficient searches for similar subsequences of different lengths in sequence databases

We propose an indexing technique for fast retrieval of similar subsequences using time warping distances. A time warping distance is a more suitable similarity measure than the Euclidean distance in many applications, where sequences may be of different lengths or different sampling rates. Our index...

Full description

Saved in:
Bibliographic Details
Main Authors: Park, S., Chu, W.W., Yoon, J., Hsu, C.
Format: Conference Proceeding
Language:English
Subjects:
Acceleration
Euclidean distance
Filters
Indexing
Information retrieval
Length measurement
Query processing
Sampling methods
Time measurement
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose an indexing technique for fast retrieval of similar subsequences using time warping distances. A time warping distance is a more suitable similarity measure than the Euclidean distance in many applications, where sequences may be of different lengths or different sampling rates. Our indexing technique uses a disk-based suffix tree as an index structure and employs lower-bound distance functions to filter out dissimilar subsequences without false dismissals. To make the index structure compact and thus accelerate the query processing, we convert sequences of continuous values to sequences of discrete values via a categorization method and store only a subset of suffixes whose first values are different from their preceding values. The experimental results reveal that our proposed technique can be a few orders of magnitude faster than sequential scanning.
ISSN:1063-6382
2375-026X
DOI:10.1109/ICDE.2000.839384