Tag
one-pass
- Jun 17, 2024 Reservoir Sampling and Priority Sampling on a Single Pass How to hold a uniform sample of a stream of unknown length with one pass, how priority sampling generalises it to weighted elements with unbiased totals, and where the sample stops being uniform. algorithms
- Jul 20, 2023 The Streaming Model: One Pass, Sublinear Space, Approximate Answers What the one-pass model forbids, how cash-register and turnstile streams differ, and why exact answers cost linear space while sketches can be merged by addition. algorithms