A stratified sampling algorithm for landmark windows over data streams

In many applications, data does not take the form of traditional stored relations, but rather arrives in continuous, rapid, time-varying data streams,and data streams are potentially unbounded in size. Focusing on the problem of sampling from landmark windows over data streams, a new concept, which is called stratified sampling ratio function, is presented. Then a multistage stratified sampling algorithm for landmark window model is introduced. In the algorithm, a dynamic candidate sample set is maintained. When an arrived tuple is determined to enter the sample set and to be deleted from the sample, the arrival time of data items is considered, and the probability for selecting to enter and remain in the sample set of more recent arrived tuples is greater than that of older ones. The theoretic analysis and experiments show that the algorithm is effective and efficient for continuous data streams processing.