Time series subsequence searching in specialized binary tree

Tak Chung Fu, Hak Pun Chan, Fu Lai Korris Chung, Chak Man Ng

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

4 Citations (Scopus)

Abstract

Subsequence searching is a non-trivial task in time series data analysis and mining. In recent years, different approaches are published to improve the performance of subsequence searching which based on index the time series and lower bound the Euclidean distance. In this paper, the problem of applying Euclidean distance on time series similarity measure is first reviewed. Previous approaches to align time series for similarity measure are then adopted for subsequence searching, they include: dynamic time warping (DTW) and perceptually important point (PIP). Furthermore, a tree data structure (SB-Tree) is developed to store the PIP of a time series and an approximate approach is proposed for subsequence searching in the SB-Tree. The experimental results performed on both synthetic and real datasets showed that the PIP approach outperformed DTW. The approximate approach based on SB-Tree can further improve the performance of the PIP-based subsequence searching while the accuracy can still be maintained.
Original languageEnglish
Title of host publicationFuzzy Systems and Knowledge Discovery - Third International Conference, FSKD 2006, Proceedings
PublisherSpringer Verlag
Pages568-577
Number of pages10
ISBN (Print)3540459162, 9783540459163
Publication statusPublished - 1 Jan 2006
Event3rd International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2006 - Xi'an, China
Duration: 24 Sep 200628 Sep 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4223 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2006
CountryChina
CityXi'an
Period24/09/0628/09/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this