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.
No takes yet. Share an insight, caveat, or question.
Ahrens et al. (1985) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: