Online maintenance of very large random samples

ABSTRACT

Random sampling is one of the most fundamental data management tools available. However, most current research involving sampling considers the problem of how to use a sample, and not how to compute one. The implicit assumption is that a "sample" is a small data structure that is easily maintained as new data are encountered, even though simple statistical arguments demonstrate that very large samples of gigabytes or terabytes in size can be necessary to provide high accuracy. No existing work tackles the problem of maintaining very large, disk-based samples from a data management perspective, and no techniques now exist for maintaining very large samples in an online manner from streaming data. In this paper, we present online algorithms for maintaining on-disk samples that are gigabytes or terabytes in size. The algorithms are designed for streaming data, or for any environment where a large sample must be maintained online in a single pass through a data set. The algorithms meet the strict requirement that the sample always be a true, statistically random sample (without replacement) of all of the data processed thus far. Our algorithms are also suitable for biased or unequal probability sampling.

REFERENCES

• 1: Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala, Congressional samples for approximate answering of group-by queries, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.487-498, May 15-18, 2000, Dallas, Texas, United States
• 2: Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala , Sridhar Ramaswamy, Join synopses for approximate query answering, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.275-286, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 3: Brian Babcock , Mayur Datar , Rajeev Motwani, Sampling from a moving window over streaming data, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.633-634, January 06-08, 2002, San Francisco, California
• 4: Brian Babcock , Surajit Chaudhuri , Gautam Das, Dynamic sample selection for approximate query processing, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872822]
• 5: Surajit Chaudhuri , Gautam Das , Vivek Narasayya, A robust, optimization-based approach for approximate answering of aggregate queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.295-306, May 21-24, 2001, Santa Barbara, California, United States
• 6: Surajit Chaudhuri , Gautam Das , Mayur Datar , Rajeev Motwani , Vivek R. Narasayya, Overcoming Limitations of Sampling for Aggregation Queries, Proceedings of the 17th International Conference on Data Engineering, p.534-542, April 02-06, 2001
• 7: W. Cochran. Sampling Techniques. Wiley & Sons, 1977
• 8: Abhinandan Das , Johannes Gehrke , Mirek Riedewald, Approximate join processing over data streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872765]
• 9: Alin Dobra , Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Processing complex aggregate queries over data streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564699]
• 10: Dimitrios Gunopulos , George Kollios , Vassilis J. Tsotras , Carlotta Domeniconi, Approximating multi-dimensional aggregate range queries over real attributes, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.463-474, May 15-18, 2000, Dallas, Texas, United States
• 11: C. Fan, M. Muller, I. Rezucha: Development of sampling plans by using sequential (item by item) techniques and digital computers. J. Amer. Stat. Assoc. 57: 387--402 (1962)
• 12: Sumit Ganguly , Phillip B. Gibbons , Yossi Matias , Avi Silberschatz, Bifocal sampling for skew-resistant join size estimation, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.271-281, June 04-06, 1996, Montreal, Quebec, Canada
• 13: Venkatesh Ganti , Mong-Li Lee , Raghu Ramakrishnan, ICICLES: Self-Tuning Samples for Approximate Query Answering, Proceedings of the 26th International Conference on Very Large Data Bases, p.176-187, September 10-14, 2000
• 14: Johannes Gehrke , Flip Korn , Divesh Srivastava, On computing correlated aggregates over continual data streams, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.13-24, May 21-24, 2001, Santa Barbara, California, United States
• 15: Phillip B. Gibbons , Yossi Matias , Viswanath Poosala, Fast incremental maintenance of approximate histograms, ACM Transactions on Database Systems (TODS), v.27 n.3, p.261-298, September 2002 [doi>10.1145/581751.581753]
• 16: Peter J. Haas , Joseph M. Hellerstein, Ripple joins for online aggregation, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.287-298, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 17: Joseph M. Hellerstein , Ron Avnur , Vijayshankar Raman, Informix under CONTROL: Online Query Processing, Data Mining and Knowledge Discovery, v.4 n.4, p.281-314, October 2000 [doi>10.1023/A:1009835310546]
• 18: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 19: C. Jermaine: Robust Estimation With Sampling and Approximate Pre-Aggregation. VLDB 2003: 886--897
• 20: T. Joens: A note on sampling from a tape file. Comm. ACM: 5, 343 (1964)
• 21: N. L. Johnson and S. Kotz: Discrete Distributions. Houghton Mifflin, 1969.
• 22: F. Olken , D. Rotem, Random sampling from B+ trees, Proceedings of the 15th international conference on Very large data bases, p.269-277, July 1989, Amsterdam, The Netherlands
• 23: Frank Olken , Doron Rotem, Random Sampling from Database Files: A Survey, Proceedings of the 5th International Conference SSDBM on Statistical and Scientific Database Management, p.92-111, April 03-05, 1990
• 24: Frank Olken , Doron Rotem , Ping Xu, Random sampling from hash files, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.375-386, May 23-26, 1990, Atlantic City, New Jersey, United States
• 25: J. Shao: Mathematical Statistics. Springer-Verlag, 1999
• 26: Hannu Toivonen, Sampling Large Databases for Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.134-145, September 03-06, 1996
• 27: 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]
• 28: Jeffrey Scott Vitter, An efficient algorithm for sequential random sampling, ACM Transactions on Mathematical Software (TOMS), v.13 n.1, p.58-67, March 1987 [doi>10.1145/23002.23003]
• 29: Jeffrey Scott Vitter , Min Wang, Approximate computation of multidimensional aggregates of sparse data using wavelets, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.193-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States