For a multi-billion-row impression log, when does reservoir sampling beat stratified sampling for an assembly job?
answer
- one pass, unknown length
- keep row i with probability k over i
- uniform means faithful, including the rarity
- strata get their own rates
- one reservoir per stratum
basics
~20 sWhen you need a faithful, unbiased miniature of the log and cannot pre-count or pre-key it — a single streaming pass of unknown length. It is the wrong pick when a rare class must be over-represented, which is the usual case for click data.
solid answer
~50 sReservoir sampling (Algorithm R) draws a uniform sample of fixed size `k` in one pass over a stream whose length need not be known: fill the reservoir with the first `k` rows, then keep row `i` with probability `k/i`, evicting a random occupant. That gives a faithful miniature — which is exactly its limitation, because a faithful miniature of a 0.1% click log is 0.1% clicks. Stratified sampling instead keys each row (clicked or not, perhaps also placement or country) and samples each stratum at its own rate: all positives, one non-click in a hundred. It needs the stratum key available at sampling time, which means the label join has already run, and it needs the per-stratum rates recorded so weights can restore the population. Choose the reservoir for unbiased miniatures and bounded memory; choose strata when a rare class must survive.
go deeper
The distinction to hold: one method gives you a smaller copy with the same mix, the other deliberately changes the mix so rare rows survive. Which you want depends on whether rarity is the point.
Explain Algorithm R's keep-with-probability-k-over-i step and why it yields uniformity without knowing the length, then explain what a stratum key costs you in extra passes and in bookkeeping.
Argue the pick from the pipeline's constraints: whether the label is available at sampling time, whether memory is bounded, and how the realised rates get recorded so the population can be reconstructed later.
The broader trade is between a single sampling policy everyone understands and per-slice policies that serve each consumer better but multiply the bookkeeping every downstream reader must honour.
## Algorithm R in one paragraph Reservoir sampling solves a specific problem: draw a uniform sample of exactly `k` items from a sequence of unknown length, in one pass, holding only `k` items in memory. Fill the reservoir with the first `k` rows. For each subsequent row `i`, keep it with probability `k/i`, and if kept, evict a uniformly chosen occupant. Every row that has passed through the stream ends with the same probability `k/n` of being in the final sample. Its properties are exactly the ones a large-log pipeline likes: **one pass**, **`O(k)` memory**, **no prior count**, and no second scan to normalise probabilities. ## What uniformity costs on a rare positive Uniformity is the guarantee and also the problem. Drawing 10,000,000 rows uniformly from a log whose click rate is 0.1% yields about **10,000 clicks**. The sample is a perfect scale model of the log, and it is a poor training set for a click model: 99.9% of the rows carry the abundant, redundant class, and the scarce class — the one every positive gradient comes from — has been thinned by the same factor as everything else. ## Stratified sampling Stratified sampling assigns each row to a stratum and gives each stratum its own rate. For click data the natural strata are the label itself (take all positives, one non-click in a hundred), often crossed with a dimension that matters operationally — placement, country, device class — so that thin slices are not sampled into nonexistence. What it demands in return: - **The stratum key must exist at sampling time.** If the key is the label, the label join has to run first, which means sampling happens after assembly rather than as a cheap filter on the raw log. - **The per-stratum rates must be recorded** with the dataset, because the sample no longer represents any real population until weights are applied. - **Thin strata need a floor**, or a small slice sampled at a uniform rate disappears and the model becomes blind to it. ## Side by side | property | reservoir sampling | stratified sampling | |---|---|---| | population size needed in advance | no | effectively yes, per stratum | | passes over the data | one | one if the key is already on the row, otherwise two | | memory | fixed, `O(k)` | one accumulator per stratum | | class balance of the result | identical to the source | deliberately changed | | rare class retention | proportional, so poor | complete, by construction | | reweighting needed afterwards | no | yes, and the rates must travel with the rows | ## When each is genuinely right - **Reservoir sampling** — when the sample must be an unbiased miniature: a debugging extract, a sanity sample used to measure the true base rate, a fixed-budget sample of a stream whose length is unknown at the time you start reading, or any case where holding more than `k` rows is impossible. - **Stratified sampling** — when a class or a slice is rare and must be over-represented so the training job sees enough of it. For click, conversion or fraud data this is nearly always the answer, and it is why the assembly job pairs it with per-row weights. ## The hybrid worth knowing The two compose: run **one reservoir per stratum**, each with its own target size, in a single pass. You get fixed, predictable memory and a guaranteed count per stratum without knowing any stratum's population in advance — the reservoir's streaming property with the stratified sample's composition. The effective per-stratum rate is then whatever `k_s / n_s` turned out to be, so each stratum's realised count and its population count must both be recorded for the weights to be computable afterwards. Weighted reservoir variants take this further by letting each row carry a sampling weight, which is useful when rows already have an importance attached — but the accounting obligation is the same: whatever tilted the sample has to be written down, or the resulting dataset cannot be mapped back to the population it came from.
- Why does stratified sampling usually force the label join to run before the sampling step?Because the stratum key is the label. You cannot take all positives and one non-click in a hundred until you know which rows are positives, and that is only known once the attribution window has closed and the join has run. So the cheap idea — sample the raw log first to make everything downstream smaller — is unavailable for label strata; the assembly job pays for a full-volume join and samples afterwards, unless it can stratify on something known at serve time instead.
- What does a per-stratum floor protect against?A slice sampled into nonexistence. If a small placement contributes a tiny fraction of traffic and every stratum is sampled at the same rate, its rows can round to almost nothing, and the model is trained as if that slice barely existed while production keeps serving it. A minimum count per stratum keeps it represented; the price is that its rows are over-represented relative to traffic, which the recorded rate and the per-row weight then correct.
saying these in an interview costs you the question
- Thinks reservoir sampling keeps rare rows preferentially.
- Says a uniform sample of an imbalanced log fixes the imbalance.
- Believes reservoir sampling needs the total row count in advance.
- Stratifies on the label without recording the per-stratum rates.
- Lets a thin slice vanish because no per-stratum floor was set.