Chinese Journal of Computers   Full Text
Title	Underlying Techniques of Efficient Similarity Search on Time Series
Authors	FENG Yu-Cai JIANG Tao LI Guo-Hui ZHU Hong
Address	(College of Computer Science & Technology, Huazhong University of Science and Technology, Wuhan 430074)
Year	2009
Issue	No.11(2107—2122)
Abstract &   Background	Abstract Time series similarity search is regarded as one of the most promising technologies in the future. However, time series data is a typical high dimensional and massive data. Developing efficient algorithms is very important for fast time series similarity queries. The paper provides an overview of research progress, and gives main research content and directions in the field. Then, some paradigms in time series applications are introduced and the performance of some typical algorithms is analyzed quantitatively. Next, this paper surveys the underlying technologies of efficient similarity queries on time series, such as bounding filtering, triangle inequality pruning, multi-resolution approach, and filter-refine scheme, etc. Furthermore, the main methods for approximate similarity search are summarized and analyzed. All above-mentioned technologies, the pros and cons of the techniques are discussed by comparison. Finally, some possible research hotspot and directions in the future are given. Keywords time series; similarity search; efficient searching methods; subsequence Background At present, there are more and more time series data owing to its wide application in many domains, such as finance data analysis, Internet traffic analysis, sensor network monitoring, moving object tracking and motion capture. On one hand, it is owing to the increase of user requirement; on the other hand, many data in other domains can be transformed into time series. However, time series data is a typical high dimension and massive data. How to improve the efficiency of similarity search is a key problem on time series. The paper focuses on the efficiency analysis and discussion of time series similarity search. This subject is supported by the National High Technology Development Program (863 Program) of China under grant Nos.2007AA01Z309, 2006AA01Z430. These projects focus on research and development of database management system. The team has made a lot of progress in the area of DBMS and published nearly 20 papers in international and domestic journals or conference proceedings. Although many similarity search algorithms are proposed for time series, however the efficiency of these algorithms still needs to improve and can’t satisfy the practical demand. The content of this paper mainly provides a summary for previous works and helps researchers pay attention to the interesting issues need to address.