Open Access Open Access  Restricted Access Subscription or Fee Access

Similarity Search in Recent Biased Data Stream with Sliding Windows

D. Muruga Radha Devi, P. Thambidurai


Similarity search in time series databases is an important research direction. Research in this field has focused on the development of effective transformation techniques, the application of dimensionality reduction methods and the design of efficient indexing schemes. In the case where time series are continuously updated with new values (streaming time series), the similarity problem becomes even more difficult to solve, since we must take into consideration the new values of the series. The challenge in a streaming database is to provide efficient algorithms and access methods for query processing, taking into consideration the fact that the database changes continuously as new data become available. Traditional access methods that continuously update the data are considered inappropriate, due to significant update costs. To attack the problem, significant research has been performed towards the development of effective and efficient methods for streaming time series processing. In this paper, we introduce the most important issues concerning similarity search in recent biased time series databases, presenting an efficient technique for similarity query processing in streaming time series using sliding windows. The proposed method called as adaptive stream processing is based on an incremental computation of Discrete wavelet transform which is used as a feature extraction method. In order to prove the efficiency of the proposed method, experiments have been performed for range query and k-nearest neighbor query on real-life data sets. The results have shown that the adaptive stream processing method exhibit consistently better performance in comparison to previously proposed approaches.


Similarity Search, Recent Biased Time Series, Sliding Window, Feature Extraction, Stream Processing.

Full Text:



Agrawal, R. Faloutsos, C & Swami.A. 1993, Efficient similarity search in sequence databases, Proceedings of the 4th Conference on Foundations Of Data organization and Algorithms.

B.Babcock, M.Datar R.Motwani, L. O‟Callaghan, Maintaining variance and k-medians over data stream windows, in Proceedings of the symposium on Principles of Database Systems,2003, pp 234 – 243.

K.P. Chan and A.W. Fu, 1999, Efficient Time Series Matching by Wavelets, Proc. Int‟l Conf on Data Eng. (ICDE 99).

Eamon Keogh, Kaushik Chakraborti, Michael Pazzani, Sharad Mehrotra, 2002, Locally Adaptive Dimensionality Reduction for indexing Large Time Series databases -ACM Transactions on Database Systems.

Eamon Keogh, Kaushik.Chakrabti, Michael Pazzani and Sharad Mehrota, 2001, Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases, Knowledge and Information Systems, vol 3, pp 263-286.

A.Guttman, R-Trees: A dynamic index structure for spatial searching, 1984, In Proceedings of ACM SIGMOD Int. Conf. Management of Data, Boston, USA , pp 47-57.

Maria Kontaki, Apostolos N Papadopoulos, Yannis Manolopoulos, Adaptive Similarity Search in streaing time series with sliding windows, Data and Knowledge Engineering , 2007, pp 478 – 502.

Rafiei , On Similarity based queries for time series data, in Proceedings of Int. Conf Data, Engineering, Sydney, Australia, 199, pp. 410-417

R. Weber, H.J.Schek and S.Blott, A quantitative analysis and performance study for similarity search methods in high-dimensional spaces, In Proceedings of Int. Conf. on very large Data bases, pp 194 – 205, New York, August 1998.

Yanchang Zhao, Shichao Zgang, 2006, Generalized Dimension Reduction Framework For Recent-Biased Time Series Analysis, IEEE Transactions on Knowledge and Data Engineering, vol 18, No 2, February 2006.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.