PGG: An Online Pattern Based Approach for Stream Variation Management

Many database applications require efficient processing ofdata streams with value variations and fluctuant sampling frequency.The variations typically imply fundamental features of the stream andimportant domain knowledge of underlying objects. In some datastreams, successive events seem to recur in a certain time interval,but the data indeed evolves with tiny differences as time elapses. Thisfeature, so called \it pseudo periodicity, poses a new challenge tostream variation management. This study focuses on the onlinemanagement for variations over such streams. The idea can be applied tomany scenarios such as patient vital signal monitoring in medicalapplications. This paper proposes a new method named Pattern GrowthGraph (PGG) to detect and manage variations over evolving streams withfollowing features: 1) adopts the wave-pattern to capture the majorinformation of data evolution and represent them compactly; 2) detectsthe variations in a single pass over the stream with the help ofwave-pattern matching algorithm; 3) only stores different segments ofthe pattern for incoming stream, and hence substantially compresses thedata without losing important information; 4) distinguishes meaningfuldata changes from noise and reconstructs the stream with acceptableaccuracy. Extensive experiments on real datasets containing millions ofdata items, as well as a prototype system, are carried out todemonstrate the feasibility and effectiveness of the proposed scheme.