STAGGER: Periodicity l\1ining of Data Streams using Expanding Sliding Windows *

Sensor devices are becoming ubiquitous, especially in measurement and monitor-ing 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 papeL 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 \vhole stream. Larger-length sliding windows are able to discover longer pe-riodicity rates. STAGGER incrementally maintains a tree-like data structure for th