Sequential random sampling

Joachim Ahrens; Ulrich Dieter

doi:10.1145/214392.214402

Sequential random sampling

Joachim Ahrens, Ulrich Dieter

Publikation: Beitrag in einer Fachzeitschrift › Artikel › Begutachtung

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.

Originalsprache	englisch
Seiten (von - bis)	157-169
Fachzeitschrift	ACM Transactions on Mathematical Software
Jahrgang	11
Ausgabenummer	2
DOIs	https://doi.org/10.1145/214392.214402
Publikationsstatus	Veröffentlicht - 1985
Extern publiziert	Ja

Treatment code (Nähere Zuordnung)

Basic - Fundamental (Grundlagenforschung)

Zugriff auf Dokument

10.1145/214392.214402

Erzeugung von Zufallszahlen
Dieter, U. & Stadlober, E.
1/01/95 → 31/12/05
Projekt: Arbeitsgebiet

Dieses zitieren

@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)

Zugriff auf Dokument

Fingerprint

Projekte

Erzeugung von Zufallszahlen

Dieses zitieren