The TS-Tree: Efficient Time Series Search and Retrieval

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Ira Assent
  • Ralph Krieger, RWTH Aachen University, Germany
  • Farzad Afschari, RWTH Aachen University, Germany
  • Thomas Seidl, RWTH Aachen University, Germany

Continuous growth in sensor data and other temporal data increases the importance of retrieval and similarity search in time series data. Efficient time series query processing is crucial for interactive applications. Existing multidimensional indexes like the R-tree provide efficient querying for only relatively few dimensions. Time series are typically long which corresponds to extremely high dimensional data in multidimensional indexes. Due to massive overlap of index descriptors, multidimensional indexes degenerate for high dimensions and access the entire data by random I/O. Consequently, the efficiency benefits of indexing are lost.

In this paper, we propose the TS-tree (time series tree), an index structure for efficient time series retrieval and similarity search. Exploiting inherent properties of time series quantization and dimensionality reduction, the TS-tree indexes high-dimensional data in an overlap-free manner. During query processing, powerful pruning via quantized separator and meta data information greatly reduces the number of pages which have to be accessed, resulting in substantial speed-up. In thorough experiments on synthetic and real world time series data we demonstrate that our TS-tree outperforms existing approaches like the R*-tree or the quantized A-tree.

Original languageEnglish
Title of host publicationProceedings of the 11th international conference on Extending database technology : Advances in database technology
Number of pages12
Volume261
Publication year2008
Pages252-263
ISBN (print)978-1-59593-926-5
ISBN (Electronic)978-1-59593-926-5
DOIs
Publication statusPublished - 2008
Externally publishedYes

See relations at Aarhus University Citationformats

ID: 47659997