Time series indexing by dynamic covering with cross-range constraints

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

Research output: Contribution to journalArticleScientificpeer-review

10 Downloads (Pure)

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
JournalVLDB JOURNAL
DOIs
Publication statusPublished - 28 May 2020
MoE publication typeA1 Journal article-refereed

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