Sequential random sampling

Joachim Ahrens; Ulrich Dieter

doi:10.1145/214392.214402

Sequential random sampling

Joachim Ahrens, Ulrich Dieter

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	157-169
Journal	ACM Transactions on Mathematical Software
Volume	11
Issue number	2
DOIs	https://doi.org/10.1145/214392.214402
Publication status	Published - 1985
Externally published	Yes

Treatment code (Nähere Zuordnung)

Basic - Fundamental (Grundlagenforschung)

Access to Document

10.1145/214392.214402

Random Number Generation
Dieter, U. & Stadlober, E.
1/01/95 → 31/12/05
Project: Research area

Cite this

@article{031144f329c14cc58fd134a9ebe201a6,

title = "Sequential random sampling",

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.",

author = "Joachim Ahrens and Ulrich Dieter",

year = "1985",

doi = "10.1145/214392.214402",

language = "English",

volume = "11",

pages = "157--169",

journal = "ACM Transactions on Mathematical Software",

issn = "1557-7295 ",

publisher = "Association of Computing Machinery",

number = "2",

}

TY - JOUR

T1 - Sequential random sampling

AU - Ahrens, Joachim

AU - Dieter, Ulrich

PY - 1985

Y1 - 1985

N2 - 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.

AB - 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.

U2 - 10.1145/214392.214402

DO - 10.1145/214392.214402

M3 - Article

SN - 1557-7295

VL - 11

SP - 157

EP - 169

JO - ACM Transactions on Mathematical Software

JF - ACM Transactions on Mathematical Software

IS - 2

ER -

Sequential random sampling

Abstract

Treatment code (Nähere Zuordnung)

Access to Document

Fingerprint

Projects

Random Number Generation

Cite this