Random sampling with a reservoir

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Random sampling with a reservoir

Full text

Pdf (1.51 MB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 11 , Issue 1 (March 1985) table of contents

Pages: 37 - 57

Year of Publication: 1985

ISSN:0098-3500

Author

Jeffrey S. Vitter

Brown Univ., Providence, RI

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 145, Citation Count: 105

Additional Information:

abstract references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/3147.3165 What is a DOI?

ABSTRACT

We introduce fast algorithms for selecting a random sample of n records without replacement from a pool of N records, where the value of N is unknown beforehand. The main result of the paper is the design and analysis of Algorithm Z; it does the sampling in one pass using constant space and in O(n(1 + log(N/n))) expected time, which is optimum, up to a constant factor. Several optimizations are studied that collectively improve the speed of the naive version of the algorithm by an order of magnitude. We give an efficient Pascal-like implementation that incorporates these modifications and that is suitable for general use. Theoretical and empirical results indicate that Algorithm Z outperforms current methods by a significant margin.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BENTLEY, J.L. Personal communication, Apr. 1983; see {11}.
	2	ERNVALL, J. AND NEVALAINEN, O. An algorithm for unbiased random sampling. Comput. J. 25, 1 (Jan. 1982), 45-47.
	3	FAN, C. T., MULLER, M. E., AND REZUCHA, I. Development of sampling plans by using sequential (item by item) selection techniques and digital computers. Am. Stat. Assoc. J. 57 (June 1962), 387-402.
	4	FELLER, W. An Introduction to Probability Theory and Its Applications, vol. I, 3rd ed. Wiley, 1968.
	5	FELLER, W. An Introduction to Probability Theory and Its Applications, vol. II, 2nd ed. Wiley, 1971.
	6	T. G. Jones, A note on sampling a tape-file, Communications of the ACM, v.5 n.6, p.343, June 1962 [doi>10.1145/367766.368159]
	7	KAWARASAKI, J., AND SIBUYA, M. Random numbers for simple random sampling without replacement. Keio Math. Sere. Rep. No. 7 (1982), 1-9.
	8	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	9	Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
	10	Jeffrey Scott Vitter, Faster methods for random sampling, Communications of the ACM, v.27 n.7, p.703-718, July 1984 [doi>10.1145/358105.893]
	11	VITTER, J.S. Optimum algorithms for two random sampling problems. In Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science (Tucson, Az., Nov. 7-9), IEEE, New York, 1983 pp. 65-75.

CITED BY 105

	Navin Kabra , David J. DeWitt, Efficient mid-query re-optimization of sub-optimal query execution plans, ACM SIGMOD Record, v.27 n.2, p.106-117, June 1998
	Noga Alon , Phillip B. Gibbons , Yossi Matias , Mario Szegedy, Tracking join and self-join sizes in limited storage, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.10-20, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, CURE: an efficient clustering algorithm for large databases, ACM SIGMOD Record, v.27 n.2, p.73-84, June 1998
	Yossi Matias , Jeffrey Scott Vitter , Min Wang, Wavelet-based histograms for selectivity estimation, ACM SIGMOD Record, v.27 n.2, p.448-459, June 1998
	Surajit Chaudhuri , Gautam Das , Vivek Narasayya, A robust, optimization-based approach for approximate answering of aggregate queries, ACM SIGMOD Record, v.30 n.2, p.295-306, June 2001
	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
	Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , Eugene J. Shekita, Improved histograms for selectivity estimation of range predicates, ACM SIGMOD Record, v.25 n.2, p.294-305, June 1996
	Frank Olken , Doron Rotem , Ping Xu, Random sampling from hash files, ACM SIGMOD Record, v.19 n.2, p.375-386, Jun. 1990
	Yannis Theodoridis , Emmanuel Stefanakis , Timos Sellis, Efficient Cost Models for Spatial Queries Using R-Trees, IEEE Transactions on Knowledge and Data Engineering, v.12 n.1, p.19-32, January 2000
	Kim-Hung Li, Reservoir-sampling algorithms of time complexity O(n(1 + log(N/n))), ACM Transactions on Mathematical Software (TOMS), v.20 n.4, p.481-493, Dec. 1994
	Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, ACM SIGMOD Record, v.27 n.2, p.331-342, June 1998
	Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, ACM SIGMOD Record, v.28 n.2, p.263-274, June 1999
	Yannis Theodoridis , Timos Sellis, A model for the prediction of R-tree performance, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.161-171, June 04-06, 1996, Montreal, Quebec, Canada
	Christopher R. Palmer , Christos Faloutsos, Density biased sampling: an improved method for data mining and clustering, ACM SIGMOD Record, v.29 n.2, p.82-92, June 2000
	Dan E. Willard, Optimal sample cost residues for differential database batch query problems, Journal of the ACM (JACM), v.38 n.1, p.104-119, Jan. 1991
	Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Random sampling techniques for space efficient online computation of order statistics of large datasets, ACM SIGMOD Record, v.28 n.2, p.251-262, June 1999
	John Byers , Jeffrey Considine , Michael Mitzenmacher , Stanislav Rost, Informed content delivery across adaptive overlay networks, ACM SIGCOMM Computer Communication Review, v.32 n.4, October 2002
	Antonios Deligiannakis , Nick Roussopoulos, Extended wavelets for multiple measures, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	George Kollios , Dimitrios Gunopulos , Nick Koudas , Stefan Berchtold, Efficient Biased Sampling for Approximate Clustering and Outlier Detection in Large Data Sets, IEEE Transactions on Knowledge and Data Engineering, v.15 n.5, p.1170-1187, September 2003
	Arvind Arasu , Brian Babcock , Shivnath Babu , Jon McAlister , Jennifer Widom, Characterizing memory requirements for queries over continuous data streams, ACM Transactions on Database Systems (TODS), v.29 n.1, p.162-194, March 2004
	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
	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
	P. Bodorik , J. Pyra , J. S. Riordon, Correcting execution of distributed queries, Proceedings of the second international symposium on Databases in parallel and distributed systems, p.192-201, July 02-04, 1990, Dublin, Ireland
	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
	P. Bodorik , J. S. Riordan , J. S. Pyra, Deciding to Correct Distributed Query Processing, IEEE Transactions on Knowledge and Data Engineering, v.4 n.3, p.253-265, June 1992
	John W. Byers , Jeffrey Considine , Michael Mitzenmacher , Stanislav Rost, Informed content delivery across adaptive overlay networks, IEEE/ACM Transactions on Networking (TON), v.12 n.5, p.767-780, October 2004
	Nina Mishra , Dana Ron , Ram Swaminathan, A New Conceptual Clustering Framework, Machine Learning, v.56 n.1-3, p.115-151
	Christopher Jermaine , Abhijit Pol , Subramanian Arumugam, Online maintenance of very large random samples, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	Subhash Suri , Csaba D. Tóth , Yunhong Zhou, Range counting over multidimensional data streams, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Nick Duffield , Carsten Lund , Mikkel Thorup, Flow sampling under hard resource constraints, ACM SIGMETRICS Performance Evaluation Review, v.32 n.1, June 2004
	Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001
	Arvind Arasu , Gurmeet Singh Manku, Approximate counts and quantiles over sliding windows, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Guojun Gan , Jianhong Wu, Subspace clustering for high dimensional categorical data, ACM SIGKDD Explorations Newsletter, v.6 n.2, December 2004
	M. H. Ali , Walid G. Aref , Cristina Nita-Rotaru, SPASS: scalable and energy-efficient data acquisition in sensor databases, Proceedings of the 4th ACM international workshop on Data engineering for wireless and mobile access, June 12-12, 2005, Baltimore, MD, USA
	Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Domain-Driven Data Synopses for Dynamic Quantiles, IEEE Transactions on Knowledge and Data Engineering, v.17 n.7, p.927-938, July 2005
	Aris Anagnostopoulos , Andrei Z. Broder , David Carmel, Sampling search-engine results, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
	Theodore Johnson , S. Muthukrishnan , Irina Rozenbaum, Sampling algorithms in a stream operator, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Graham Cormode , S. Muthukrishnan , Irina Rozenbaum, Summarizing and mining inverse distributions on data streams via dynamic inverse sampling, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	H. Wang , S. Parthasarathy , A. Ghoting , S. Tatikonda , G. Buehrer , T. Kurc , J. Saltz, Design of a next generation sampling service for large scale data analysis applications, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts
	João Pedro Costa , Pedro Furtado, DSQoS-distributed architecture providing QoS in summary warehouses, Proceedings of the 6th ACM international workshop on Data warehousing and OLAP, November 07-07, 2003, New Orleans, Louisiana, USA
	Georgia Koloniari , Yannis Petrakis , Evaggelia Pitoura , Thodoris Tsotsos, Query workload-aware overlay construction using histograms, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
	Alexandros Nanopoulos , Yannis Manolopoulos , Yannis Theodoridis, An efficient and effective algorithm for density biased sampling, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
	Frank Olken , Doron Rotem, Random sampling from database files: a survey, Proceedings of the 5th international conference on Statistical and Scientific Database Management, p.92-111, April 03-05, 1990, Charlotte, NC
	M. Kolonko , D. Wäsch, Sequential reservoir sampling with a nonuniform distribution, ACM Transactions on Mathematical Software (TOMS), v.32 n.2, p.257-273, June 2006
	Noga Alon , Nick Duffield , Carsten Lund , Mikkel Thorup, Estimating arbitrary subset sums with few probes, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
	Pavlos S. Efraimidis , Paul G. Spirakis, Weighted random sampling with a reservoir, Information Processing Letters, v.97 n.5, p.181-185, 16 March 2006
	M. Dutta , A. Kakoti Mahanta , Arun K. Pujari, QROCK: a quick version of the ROCK algorithm for clustering of categorical data, Pattern Recognition Letters, v.26 n.15, p.2364-2373, November 2005
	Alexandros Nanopoulos , Yannis Theodoridis , Yannis Manolopoulos, Indexed-based density biased sampling for clustering applications, Data & Knowledge Engineering, v.57 n.1, p.37-63, April 2006
	A. Balmin , T. Eliaz , J. Hornibrook , L. Lim , G. M. Lohman , D. Simmen , M. Wang , C. Zhang, Cost-based optimization in DB2 XML, IBM Systems Journal, v.45 n.2, p.299-319, January 2006
	Rainer Gemulla , Wolfgang Lehner, Sampling time-based sliding windows in bounded space, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Keke Chen , Ling Liu, iVIBRATE: Interactive visualization-based framework for clustering large datasets, ACM Transactions on Information Systems (TOIS), v.24 n.2, p.245-294, April 2006
	Arvind Arasu , Shivnath Babu , Jennifer Widom, The CQL continuous query language: semantic foundations and query execution, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.121-142, June 2006
	Rainer Gemulla , Wolfgang Lehner , Peter J. Haas, A dip in the reservoir: maintaining sample synopses of evolving datasets, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Charu C. Aggarwal, On biased reservoir sampling in the presence of stream evolution, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Mario Szegedy, The DLT priority sampling is essentially optimal, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Luciana S. Buriol , Gereon Frahling , Stefano Leonardi , Alberto Marchetti-Spaccamela , Christian Sohler, Counting triangles in data streams, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Deepak Agarwal , Andrew McGregor , Jeff M. Phillips , Suresh Venkatasubramanian , Zhengyuan Zhu, Spatial scan statistics: approximations and performance study, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Xuemin Lin , Qing Zhang , Yidong Yuan , Qing Liu, Error minimization in approximate range aggregates, Data & Knowledge Engineering, v.62 n.1, p.156-176, July, 2007
	Antonios Deligiannakis , Minos Garofalakis , Nick Roussopoulos, Extended wavelets for multiple measures, ACM Transactions on Database Systems (TODS), v.32 n.2, p.10-es, June 2007
	Zhang Longbo , Li Zhanhuai , Zhao Yiqiang , Yu Min , Zhang Yang, A priority random sampling algorithm for time-based sliding windows over weighted streaming data, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
	Kevin Beyer , Peter J. Haas , Berthold Reinwald , Yannis Sismanis , Rainer Gemulla, On synopses for distinct-value estimation under multiset operations, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
	Wee Hyong Tok , Stéphane Bressan , Mong-Li Lee, A stratified approach to progressive approximate joins, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	Christopher Jermaine, Robust estimation with sampling and approximate pre-aggregation, Proceedings of the 29th international conference on Very large data bases, p.886-897, September 09-12, 2003, Berlin, Germany
	Jeffery Xu Yu , Zhihong Chong , Hongjun Lu , Aoying Zhou, False positive or false negative: mining frequent itemsets from high speed transactional data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.204-215, August 31-September 03, 2004, Toronto, Canada
	Gurmeet Singh Manku , Rajeev Motwani, Approximate frequency counts over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.346-357, August 20-23, 2002, Hong Kong, China
	Rainer Gemulla , Wolfgang Lehner , Peter J. Haas, Maintaining bernoulli samples over evolving multisets, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
	Arjun Dasgupta , Gautam Das , Heikki Mannila, A random walk approach to sampling hidden databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
	Dianxun Shuai , Yumin Dong , Qing Shuai, A new data clustering approach: Generalized cellular automata, Information Systems, v.32 n.7, p.968-977, November, 2007
	Surajit Chaudhuri , Gautam Das , Vivek Narasayya, Optimized stratified sampling for approximate query processing, ACM Transactions on Database Systems (TODS), v.32 n.2, p.9-es, June 2007
	Alexandros Nanopoulos , Yannis Theodoridis , Yannis Manolopoulos, C2P: Clustering based on Closest Pairs, Proceedings of the 27th International Conference on Very Large Data Bases, p.331-340, September 11-14, 2001
	B. R. Iyer , G. R. Ricard , P. J. Varman, Percentile finding algorithm for multiple sorted runs, Proceedings of the 15th international conference on Very large data bases, p.135-144, July 1989, Amsterdam, The Netherlands
	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
	Frank Olken , Doron Rotem, Simple Random Sampling from Relational Databases, Proceedings of the 12th International Conference on Very Large Data Bases, p.160-169, August 25-28, 1986
	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
	Phillip B. Gibbons, Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports, Proceedings of the 27th International Conference on Very Large Data Bases, p.541-550, September 11-14, 2001
	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
	Minos N. Garofalakis , Phillip B. Gibbon, Approximate Query Processing: Taming the TeraBytes, Proceedings of the 27th International Conference on Very Large Data Bases, p.725, September 11-14, 2001
	Balakrishna R. Iyer , David Wilhite, Data Compression Support in Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.695-704, September 12-15, 1994
	Viswanath Poosala , Yannis E. Ioannidis, Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing, Proceedings of the 22th International Conference on Very Large Data Bases, p.448-459, September 03-06, 1996
	Gao Cong , Wenfei Fan , Floris Geerts , Xibei Jia , Shuai Ma, Improving data quality: consistency and accuracy, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Hüseyin Akcan , Alex Astashyn , Hervé Brönnimann, Deterministic algorithms for sampling count data, Data & Knowledge Engineering, v.64 n.2, p.405-418, February, 2008
	Byung-Hoon Park , George Ostrouchov , Nagiza F. Samatova, Sampling streaming data with replacement, Computational Statistics & Data Analysis, v.52 n.2, p.750-762, October, 2007
	Marios Hadjieleftheriou , Xiaohui Yu , Nick Koudas , Divesh Srivastava, Hashed samples: selectivity estimators for set similarity selection queries, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Elad Hazan , Satyen Kale, Better algorithms for benign bandits, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.38-47, January 04-06, 2009, New York, New York
	Parikshit Gopalan , T. S. Jayram , Robert Krauthgamer , Ravi Kumar, Estimating the sortedness of a data stream, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.318-327, January 07-09, 2007, New Orleans, Louisiana
	Nick Duffield , Carsten Lund , Mikkel Thorup, Priority sampling for estimation of arbitrary subset sums, Journal of the ACM (JACM), v.54 n.6, p.32-es, December 2007
	Surong Wang , Manoranjan Dash , Liang-Tien Chia , Min Xu, Efficient sampling of training set in large and noisy multimedia data, ACM Transactions on Multimedia Computing, Communications, and Applications (TOMCCAP), v.3 n.3, p.14-es, August 2007
	Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, Why go logarithmic if we can go linear?: Towards effective distinct counting of search traffic, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	Yufei Tao , Xiang Lian , Dimitris Papadias , Marios Hadjieleftheriou, Random Sampling for Continuous Streams with Arbitrary Updates, IEEE Transactions on Knowledge and Data Engineering, v.19 n.1, p.96-110, January 2007
	Jayendra Venkateswaran , Tamer Kahveci , Christopher Jermaine , Deepak Lachwani, Reference-based indexing for metric spaces with costly distance measures, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.1231-1251, August 2008
	Abhijit Pol , Christopher Jermaine , Subramanian Arumugam, Maintaining very large random samples using the geometric file, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.997-1018, August 2008
	Peter Bertels , Wim Heirman , Dirk Stroobandt, Efficient measurement of data flow enabling communication-aware parallelisation, Proceedings of the 1st international forum on Next-generation multicore/manycore technologies, November 24-25, 2008, Cairo, Egypt
	Kun-Ta Chuang , Keng-Pei Lin , Ming-Syan Chen, Quality-Aware Sampling and Its Applications in Incremental Data Mining, IEEE Transactions on Knowledge and Data Engineering, v.19 n.4, p.468-484, April 2007
	Suman Nath , Phillip B. Gibbons, Online maintenance of very large random samples on flash storage, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Edith Cohen , Nick Duffield , Haim Kaplan , Carsten Lund , Mikkel Thorup, Stream sampling for variance-optimal estimation of subset sums, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1255-1264, January 04-06, 2009, New York, New York
	Philipp Rösch , Wolfgang Lehner, Sample synopses for approximate answering of group-by queries, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Chaitanya Mishra , Nick Koudas, The design of a query monitoring system, ACM Transactions on Database Systems (TODS), v.34 n.1, p.1-51, April 2009
	Jun-Ki Min , Chun-Hee Lee , Chin-Wan Chung, AMID: Approximation of MultI-measured Data using SVD, Information Sciences: an International Journal, v.179 n.16, p.2833-2850, July, 2009
	Kun-Ta Chuang , Hung-Leng Chen , Ming-Syan Chen, Feature-preserved sampling over streaming data, ACM Transactions on Knowledge Discovery from Data (TKDD), v.2 n.4, p.1-45, January 2009
	Vladimir Braverman , Rafail Ostrovsky , Carlo Zaniolo, Optimal sampling from sliding windows, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Edward Bortnikov , Maxim Gurevich , Idit Keidar , Gabriel Kliot , Alexander Shraer, Brahms: Byzantine resilient random membership sampling, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.53 n.13, p.2340-2359, August, 2009
	C. C. Kirkham, Ranked reservoir sampling: an extension to the reservoir sampling algorithm, Software—Practice & Experience, v.37 n.12, p.1285-1288, October 2007
	Graham Cormode , Lukasz Golab , Korn Flip , Andrew McGregor , Divesh Srivastava , Xi Zhang, Estimating the confidence of conditional functional dependencies, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
	Yi Zhang , Xiaoming Jin, Concept sampling: towards systematic selection in large-scale mixed concepts in machine learning, Proceedings of the 20th international joint conference on Artifical intelligence, p.1150-1155, January 06-12, 2007, Hyderabad, India

INDEX TERMS

Classification:
D. Software
D.4 OPERATING SYSTEMS
D.4.3 File Systems Management
Subjects: Access methods

G. Mathematics of Computing
G.3 PROBABILITY AND STATISTICS
Subjects: Probabilistic algorithms (including Monte Carlo); Random number generation; Statistical software
G.4 MATHEMATICAL SOFTWARE
Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Performance, Theory, Verification

REVIEW

"Prokop Vondracek : Reviewer"

There is presented a fast algorithm for selecting a random sample of n records without replacement for a pool of N records, where the value of N is unknown beforehand. Algorithm Z, which does the sampling, is des more...

Collaborative Colleagues:

Jeffrey S. Vitter: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player