An improved sampling algorithm for landmark windows over weighted streaming data

This paper discusses the random sampling algorithm for landmark windows over weighted streaming data, and presents a new algorithm by improving weighted random sampling (WRS) algorithm with a reservoir. When a new data item v_i with weight w_i arrives, a random number u_i is generated, and a key k_i is calculated by w_i and u_i for the data item. We maintain a candidate sample set by the keys of data items, and the keys of older data items is decreased periodically. The theoretic analysis and experiments show that the algorithm is effective and efficient for continuous data streams processing.