Time series indexing by dynamic covering with cross-range constraints

Tao Sun, Hongbo Liu*, Seán McLoone, Shaoxiong Ji, Xindong Wu

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

Time series indexing plays an important role in querying and pattern mining of big data. This paper proposes a novel structure for tightly covering a given set of time series under the dynamic time warping similarity measurement. The structure, referred to as Dynamic Covering with cross-Range Constraints (DCRC),
enables more efficient and scalable indexing to be developed than current hypercube based partitioning approaches. In particular, a lower bound of the DTW distance from a given query time series to a DCRC-based cover set is introduced. By virtue of its tightness, which is proven theoretically, the lower bound can be used for pruning when querying on an indexing tree. If the DCRC
based Lower Bound (LB DCRC) of an upper node in an index tree is larger than a given threshold, all child nodes can be pruned yielding a significant reduction in computational time. A Hierarchical DCRC (HDCRC) structure is proposed to generate the DCRC-tree based indexing and used to develop time series indexing and insertion algorithms. Experimental results for a selection of benchmark time series datasets are presented to illustrate the tightness of LB DCRC, as well as the pruning efficiency on the DCRC-tree, especially when the time series have large deformations.
Original languageEnglish
Number of pages19
JournalThe International Jounal on Very Large Data Bases
Early online date28 May 2020
Publication statusEarly online date - 28 May 2020

Keywords

  • Time Series · Dynamic Time Warping · Indexing · R-Tree · Dynamic Covering · Cross-Range Constraints

Fingerprint Dive into the research topics of 'Time series indexing by dynamic covering with cross-range constraints'. Together they form a unique fingerprint.

  • Cite this