Sampling from a moving window over streaming data

ABSTRACT

We introduce the problem of sampling from a moving window of recent items from a data stream and develop two algorithms for this problem. The first algorithm, "chain-sample", extends reservoir sampling to deal with the expiration of data elements from the sample. The expected memory usage of our algorithm is O(k) when maintaining a sample of size k over a window of the n most recent elements from the data stream, and with high probability the algorithm requires no more than O(k log n) memory.When the number of elements in the window is variable, as is the case when the size of the window is defined as a time duration rather than as a fixed number of data elements, the sampling problem becomes harder. Our second algorithm, "priority-sample", works even when the number of elements in the window can vary dynamically over time. With high probability, the "priority-sample" algorithm uses no more than O(k log n) memory.

REFERENCES

• 1: C. R. Aragon and R. G. Seidel, Randomized Search Trees, Proc. of the 30th IEEE Symp. on Foundations of Computer Science, 1989, pp. 540-545.
• 2: Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603884]
• 3: K. Mulmuley, Computational Geometry: An Introduction through Randomized Algorithms, Prentice Hall, Englewood Cliffs, New Jersey, 1994.
• 4: Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]
• 5: Phillip B. Gibbons , Yossi Matias , Viswanath Poosala, Fast Incremental Maintenance of Approximate Histograms, Proceedings of the 23rd International Conference on Very Large Data Bases, p.466-475, August 25-29, 1997
• 6: Yossi Matias , Jeffrey Scott Vitter , Min Wang, Dynamic Maintenance of Wavelet-Based Histograms, Proceedings of the 26th International Conference on Very Large Data Bases, p.101-110, September 10-14, 2000