Carnegie Mellon University
Browse

Efficient Retrieval of Similar Time Sequences under Time Warping

Download (292.28 kB)
journal contribution
posted on 1981-01-01, 00:00 authored by Byoung-Kee Yi, H. V. Jagadish, Christos Faloutsos
Fast similarity searching in large time sequence databases has typically used Euclidean distance as a dissimilarity metric. However, for several applications, including matching of voice, audio and medical signals (e.g., electrocardiograms), one is required to permit local accelerations and decelerations in the rate of sequences, leading to a popular, field tested dissimilarity metric called the “time warping” distance. From the indexing viewpoint, this metric presents two major challenges: (a) it does not lead to any natural indexable “features”, and (b) comparing two sequences requires time quadratic in the sequence length. To address each problem, we propose to use: (a) a modification of the so called “FastMap”, to map sequences into points, with little compromise of “recall” (typically zero); and (b) a fast linear test, to help us discard quickly many of the false alarms that FastMap will typically introduce. Using both ideas in cascade, our proposed method achieved up to an order of magnitude speed-up over sequential scanning on both real and synthetic datasets

History

Publisher Statement

All Rights Reserved

Date

1981-01-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC