Sequential random sampling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Sequential random sampling

Full text

Pdf (896 KB)

Source

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

Pages: 157 - 169

Year of Publication: 1985

ISSN:0098-3500

Authors

J. H. Ahrens	Mathematisches Seminar, Universität Kiel, Olshausenstrasse 40-60, D 2300 Kiel, Federal Republic of Germany
U. Dieter	Institut für Statistik, Universität Graz, Lessingstrasse 27, A 8010 Graz, Austria

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 34, Citation Count: 4

Additional Information:

abstract references cited by index terms 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/214392.214402 What is a DOI?

ABSTRACT

Fast algorithms for selecting a random set of exactly k records from a file of n records are constructed. Selection is sequential: the sample records are chosen in the same order in which they occur in the file. All procedures run in O(k) time. The “geometric” method has two versions: with or without O(k) auxiliary space. A further procedure uses hashing techniques and requires O(k) space.

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	ABRAMOWITZ, M., AND STEGUN, I.A. Handbook of Mathematical Functions, 9th ed. Dover, New York, 1972.
	2	J. H. Ahrens , U. Dieter, Computer methods for sampling from the exponential and normal distributions, Communications of the ACM, v.15 n.10, p.873-882, Oct. 1972 [doi>10.1145/355604.361593]
	3	FAN, C. W., MULLER, M. E., AND REZUCHA, I. Development of sampling plans by using sequential (item by item) selection techniques and digital computers, j. Am. Statist. Assoc. 57 (June 1962), 387-402.
	4	GEHRKE, H. Einfache sequentielle Stichprobenentnahme. Diplomarbeit, Universit~it Kiel, Kiel, West Germany, 1984.
	5	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]
	6	KAWARASAKI, J., AND SIBUYA, M. Random numbers for simple random sampling without replacement. Keio Math. Sem. Rep. No. 7 (1982).
	7	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	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	TEUI-IOLA, J., AND NEVALAINEN, O. Two efficient algorithms for random sampling without{ replacement. Int. J. Comput. Math. 11 (1982), 127-140.
	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]

CITED BY 4

	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
	Yi-Leh Wu , Divyakant Agrawal , Amr El Abbadi, Applying the golden rule of sampling for query estimation, ACM SIGMOD Record, v.30 n.2, p.449-460, June 2001
	K. Aiyappan Nair, An Improved Algorithm for Ordered Sequential Random Sampling, ACM Transactions on Mathematical Software (TOMS), v.16 n.3, p.269-274, Sept. 1990
	Ekow J. Otoo , Arie Shoshani , Seung-Won Hwang, Clustering High Dimensional Massive Scientific Datasets, Journal of Intelligent Information Systems, v.17 n.2-3, p.147-168, December 2001