Fast retrieval of similar subsequences in long sequence databases

Sanghyun Park, Dongwon Lee, Wesley W. Chu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

63 Scopus citations

Abstract

Although the Euclidean distance has been the most popular similarity measure in sequence databases, recent techniques prefer to use high-cost distance functions such as the time warping distance and the editing distance for wider applicability. However, if these distance functions are applied to the retrieval of similar subsequences, the number of subsequences to be inspected during the search is quadratic to the average length L~ of data sequences. We propose a novel subsequence matching scheme, called the aligned subsequence matching, where the number of subsequences to be compared with a query sequence is reduced to linear to L~. We also present an indexing technique to speed-up the aligned subsequence matching using the similarity measure of the modified time warping distance. Experiments on synthetic data sequences demonstrate the effectiveness of our proposed approach; ours consistently outperformed sequential scanning and achieved an up to 6.5 times speed-up.

Original languageEnglish (US)
Title of host publicationProceedings - 1999 Workshop on Knowledge and Data Engineering Exchange, KDEX 1999
EditorsPeter Scheuermann
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages60-67
Number of pages8
ISBN (Electronic)0769504531, 9780769504537
DOIs
StatePublished - Jan 1 1999
Event1999 Workshop on Knowledge and Data Engineering Exchange, KDEX 1999 - Chicago, United States
Duration: Nov 7 1999 → …

Publication series

NameProceedings - 1999 Workshop on Knowledge and Data Engineering Exchange, KDEX 1999

Other

Other1999 Workshop on Knowledge and Data Engineering Exchange, KDEX 1999
Country/TerritoryUnited States
CityChicago
Period11/7/99 → …

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'Fast retrieval of similar subsequences in long sequence databases'. Together they form a unique fingerprint.

Cite this