Construction of Synopsis for Periodically Updating Sliding Windows over Data Streams

In many applications including network monitoring, Web click stream analysis, sensor networks, detection of network intrusions, telecommunications data management and financial applications, data arrives in a stream fashion. The main focus in algorithms for data streams has been on efficient construction of synopsis data structures. This paper introduces the problem of construction of synopsis data structures from periodically updating sliding windows over data streams, and presents a new sampling-based synopsis data structure and new techniques for its fast incremental maintenance. We use the basic window technique in conjunction with reservoir sampling algorithm to present a novel algorithm, which is called RSAP Algorithm. The algorithm is not an unbiased one but a stratified unbiased random sampling algorithm. The experiments show that the new algorithm is effective and efficient for construction of summary structures from sliding windows over data streams.