Weighted random sampling with a reservoir

By Pavlos S. Efraimidis, Paul (Pavlos) Spirakis. 2006

416 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Sergey Levine
2. Stefano Ermon
3. Pieter Abbeel
4. Michalis K. Titsias
5. Ricardo Henao
6. Yoshua Bengio
7. Herke Van Hoof
8. Max Welling

In Computer Networks and Communications

1. Fanjie Kong
2. Sudipto Guha
3. Ricardo Henao
4. Ang Li
5. Max Welling
6. Michalis K. Titsias
7. Huiyi Hu
8. B. Heijmans

In Signal Processing

1. Stefano Ermon
2. Fanjie Kong
3. Sudipto Guha
4. Ricardo Henao
5. Ang Li
6. Max Welling
7. Michalis K. Titsias
8. Huiyi Hu

Citations in the corpus

• Information-theoretic Online Memory Selection for Continual Learning (2022, positive): “Algorithm 4 Weighted Reservoir Sampling (Chao, 1982; Efraimidis & Spirakis, 2006) 1: Input: BufferM, budget M , the new data point (x?, y?).”
• Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement (2019, methodology): “The Gumbel-Top-k trick is mathematically equivalent to Weighted Reservoir Sampling (Efraimidis & Spirakis, 2006), as was noted in a blog post by Vieira (2014).”
• Efficient Classification of Very Large Images with Tiny Objects (2021, methodology): “Fortunately, using a formulation similar to that of [20], we can still obtain an unbiased estimator of the average (expectation) in (6) from a non-iid sample, without replacement, by leveraging the Gumbel-Top-k trick [23], which is extended from the Gumbel-Max trick for weighted reservoir sampling [”
• Reparameterizable Subset Sampling via Continuous Relaxations (2019, methodology): “The algorithm uses TopK to return the items S wrs = [ e i 1 , . . . , e i k ] as the WRS. Efraimidis and Spirakis proved (Proposition 5 in [Efraimidis and Spirakis, 2006]) that the output of Algorithm 1 is distributed according to p ( S wrs | w ) .”
• Controlling bias and inflation in epigenome- and transcriptome-wide association studies using the empirical null distribution (2016, methodology): “We implemented the Gibbs sampling algorithm in C and can either use weighted multinomial sampling method for binned test statistics or a fast sampling method [55] if all individual test statistics are used (user-defined).”
• Robust Random Cut Forest Based Anomaly Detection on Streams (2016, background): “…of choosing an axis parallel cut that splits S ∪ {p} in dimension i, conditioned on not isolating p from all points of S. (ii) Given a random tree of RRCF (S ∪ {p}), conditioned on the fact the first cut isolates p from all points of S, the remainder of the tree is a random tree in RRCF (S).”