Weighted Random Sampling over Data Streams

The Art of Computer Programming

D.E. Knuth · 1981

Earlier work this paper cites.

A general purpose unequal probability sampling plan

M. T. Chao · 1982

Earlier work this paper cites.

Faster methods for random sampling

Jeffrey Scott Vitter · 1984

Earlier work this paper cites.

Random sampling with a reservoir

J.S. Vitter · 1985

Earlier work this paper cites.

Non-Uniform Random Variate Generation

Luc Devroye · 1986

Earlier work this paper cites.

Random Sampling from Databases

F. Olken · 1993

Earlier work this paper cites.

Reservoir-sampling algorithms of time complexity o(n(1 + log(n/n)))

Kim-Hung Li · 1994

Cited alongside, same era.

On biased reservoir sampling in the presence of stream evolution

Charu C. Aggarwal · 2006

Cited alongside, same era.

Weighted random sampling with a reservoir

Pavlos S. Efraimidis and Paul G. Spirakis · 2006

Cited alongside, same era.

A priority random sampling algorithm for time-based sliding windows over weighted streaming data

Zhang Longbo, Li Zhanhuai, Zhao Yiqiang, Yu Min, and Zhang Yang · 2007

Cited alongside, same era.

Forward decay: A practical time decay model for streaming systems

Graham Cormode, Vladislav Shkapenyuk, Divesh Srivastava, and Bojian Xu · 2009

Cited alongside, same era.

Optimal sampling from distributed streams

Graham Cormode, S. Muthukrishnan, Ke Yi, and Qin Zhang · 2010

Cited alongside, same era.

A stream sampler for weighted random sampling

WRS

Cited in the paper.

Optimal random sampling from distributed streams revisited

Srikanta Tirthapura and David P. Woodruff · 2011

Closest in time.

Continuous sampling from distributed streams

Graham Cormode, S. Muthukrishnan, Ke Yi, and Qin Zhang · 2012

Closest in time.

Adaptive stratified reservoir sampling over heterogeneous data streams

Mohammed Al-Kateb and Byung Suk Lee · 2014

Closest in time.

The case for sampling on very large file systems

G. Goldberg, D. Harnik, and D. Sotnikov · 2014

Closest in time.

Independent range sampling

Xiaocheng Hu, Miao Qiao, and Yufei Tao · 2014

Closest in time.