You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Reservoir sampling is biased toward later rows #9569
The Reservoir Sampling operator does not produce a uniform random sample. The replacement probability is off by one, so the first input tuple after the reservoir fills is always kept (probability 1.0 instead of count/(count+1)), biasing the final sample toward tuples that arrive later in the stream.
How to reproduce?
Run a workflow with a Reservoir Sampling operator (small k, e.g. 5) over an input much larger than k (100+ rows); across runs the sampled rows skew toward the end of the input. In code, ReservoirSamplingOpExec.processTuple draws rand.nextInt(n) where n is the number of tuples already seen, instead of the Algorithm R bound nextInt(n+1).
Activity