Indexing and classifying gigabytes of time series under time warping

Chang Wei Tan, Geoffrey I. Webb, Francois Petitjean

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    42 Citations (Scopus)


    Time series classification maps time series to labels. The nearest neighbour algorithm (NN) using the Dynamic Time Warping (DTW) similarity measure is a leading algorithm for this task. NN compares each time series to be classified to every time series in the training database. With a training database of N time series of lengths L, each classification requires ν(N · L 2 ) computations. The databases used in almost all prior research have been relatively small (with less than 10; 000 samples) and much of the research has focused on making DTW's complexity linear with L, leading to a runtime complexity of O(N · L). As we demonstrate with an example in remote sensing, real-world time series databases are now reaching the million-to-billion scale. This wealth of training data brings the promise of higher accuracy, but raises a significant challenge because N is becoming the limiting factor. As DTW is not a metric, indexing objects induced by its space is extremely challenging. We tackle this task in this paper. We develop TSI, a novel algorithm for Time Series Indexing which combines a hierarchy of K-means clustering with DTW-based lower-bounding. We show that, on large databases, TSI makes it possible to classify time series orders of magnitude faster than the state of the art.
    Original languageEnglish
    Title of host publicationProceedings of the 17th SIAM International Conference on Data Mining
    Subtitle of host publicationHouston, Texas, USA, 27 – 29 April , 2017
    EditorsNitesh Chawla, Wei Wang
    Place of PublicationPhiladelphia, PA
    PublisherSociety for Industrial & Applied Mathematics (SIAM)
    Number of pages9
    ISBN (Electronic)9781611974874, 9781611974881
    Publication statusPublished - 1 Jan 2017
    EventSIAM International Conference on Data Mining 2017 - Houston, United States of America
    Duration: 27 Apr 201729 Apr 2017
    Conference number: 17th


    ConferenceSIAM International Conference on Data Mining 2017
    Abbreviated titleSDM 2017
    Country/TerritoryUnited States of America


    • Dynamic time warping
    • Time series classification
    • Time series indexing

    Cite this