Login | Register

Efficient and scalable search for similar patterns in time series data


Efficient and scalable search for similar patterns in time series data

Kadiyala, Srividya (2006) Efficient and scalable search for similar patterns in time series data. Masters thesis, Concordia University.

PDF - Accepted Version


Popularity of time series databases for predicting future events and trends in applications such as market analysis and weather forecast require the development of more reliable, fast; and memory efficient indexes. In this thesis, we consider searching similar patterns in time series data for variable length queries. Recently an indexing technique called Multi-Resolution Index (MRI) has been proposed to solve this problem [Kah01, Kah04] which uses compression to reduce the index size. However, the processor workload and memory curtails the opportunity of utilizing compression as an additional step. Motivated by the need and limitations of existing techniques, the main objective of this thesis is to develop an alternative multi-resolution index structure and algorithm, to which we refer as Compact MRI (CMRI). This new technique takes advantage of an existing dimensionality reduction technique called Adaptive Piecewise Constant Approximation (APCA) [Keo01]. Advantages of CMRI is that it utilizes less space without requiring any compression and gains high precision. We have implemented MRI and CMRI and performed extensive experiments to compare them. To evaluate the precision and performance of CMRI, we have used both real and synthetic data, and compared the results with MRI. The experimental results indicate that CMRI improves precision, ranging from 0.75 to 0.89 on real data, and from 0.80 to 0.95 on synthetic data. Furthermore, CMRI is superior over MRI in performance as the number of disk I/Os required by CMRI is close to minimal. Compared to sequential scan, CMRI is 4 to 30 times faster, observed on both real and synthetic data.

Divisions:Concordia University > Faculty of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Kadiyala, Srividya
Pagination:xiii, 85 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Shiri, Nematollaah
ID Code:8949
Deposited By: Concordia University Libraries
Deposited On:18 Aug 2011 18:40
Last Modified:18 Aug 2011 19:01
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page


Downloads per month over past year

Back to top Back to top