Weighted reservoir sampling in one pass

Question

A stream emits (item, weight) pairs, with positive weights, and you never learn the length. You want a sample of k items where each item's chance of ending in the sample is proportional to its weight, not uniform. Implement weighted reservoir sampling in one pass using O(k) memory.

Accepted Answer

Uniform reservoir sampling does not generalize by "replace with probability proportional to weight," because survival across many later steps distorts the marginal. The clean trick is the Efraimidis-Spirakis A-Res algorithm: give each item a random key ui^{1/wi}, where ui is uniform on (0,1), and keep the k items with the largest keys. A size-k min-heap keyed on the smallest kept key lets you decide each item in O(\log k). Why u^{1/w} works. For a uniform u, the variable u^{1/w} has CDF P(u^{1/w} \le x) = x^{w} on (0,1). A heavier weight w pushes the key toward 1, so heavier items win the "la…

Weighted reservoir sampling in one pass

Your answer

More Coding questions