STAGGER: Periodicity Mining of Data Streams Using Expanding Sliding Windows
Authors:
- 1 December 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2 (15504786) , 188-199
Abstract
Sensor devices are becoming ubiquitous, especially in measurement and monitoring applications. Because of the real-time, append-only and semi-infinite natures of the generated sensor data streams, an online incremental approach is a necessity for mining stream data types. In this paper, we propose STAGGER: a one-pass, online and incremental algorithm for mining periodic patterns in data streams. STAGGER does not require that the user pre-specify the periodicity rate of the data. Instead, STAGGER discovers the potential periodicity rates. STAGGER maintains multiple expanding sliding windows staggered over the stream, where computations are shared among the multiple overlapping windows. Small-length sliding windows are imperative for early and real-time output, yet are limited to discover short periodicity rates. As streamed data arrives continuously, the sliding windows expand in length in order to cover the whole stream. Larger-length sliding windows are able to discover longer periodicity rates. STAGGER incrementally maintains a tree-like data structure for the frequent periodic patterns of each discovered potential periodicity rate. In contrast to the Fourier/Wavelet-based approaches used for discovering periodicity rates, STAGGER not only discovers a wider, more accurate set of periodicities, but also discovers the periodic patterns themselves. In fact, experimental results with real and synthetic data sets show that STAGGER outperforms Fourier/Wavelet-based approaches by an order of magnitude in terms of the accuracy of the discovered periodicity rates. Moreover, real-data experiments demonstrate the practicality of the discovered periodic patterns.Keywords
This publication has 6 references indexed in Scilit:
- Periodicity detection in time series databasesIEEE Transactions on Knowledge and Data Engineering, 2005
- Incremental, online, and merge mining of partial periodic patterns in time-series databasesIEEE Transactions on Knowledge and Data Engineering, 2004
- SEGMENTING TIME SERIES: A SURVEY AND NOVEL APPROACH2004
- ICD Therapy for the Prevention of Sudden Cardiac Death in Post-MI Patients.Current Treatment Options in Cardiovascular Medicine, 2003
- A review of symbolic analysis of experimental dataReview of Scientific Instruments, 2003
- A symbolic representation of time series, with implications for streaming algorithms2003