Sequential random sampling

Joachim Ahrens, Ulrich Dieter

Research output: Contribution to journalArticlepeer-review


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 languageEnglish
Pages (from-to)157-169
JournalACM Transactions on Mathematical Software
Issue number2
Publication statusPublished - 1985
Externally publishedYes

Treatment code (Nähere Zuordnung)

  • Basic - Fundamental (Grundlagenforschung)


Dive into the research topics of 'Sequential random sampling'. Together they form a unique fingerprint.

Cite this