Weighted random sampling with a reservoir

B. Babcock, S. Babu, M. Datar, R. Motwani, J. Widom, Models and issues in data stream systems, in: ACM PODS, 2002, pp. 1–16 Chaudhuri, 1999, On random sampling over joins, 263 Devroye, 1986 Karger, 1994, Random sampling in cut, flow, and network design problems, 648 Karger, 2002, Random sampling in residual graphs, 63 Knuth, 1981, Seminumerical Algorithms, vol. 2 Li, 1994, Reservoir-sampling algorithms of time complexity o(n(1+log(n/n))), ACM Trans. Math. Software, 20, 481, 10.1145/198429.198435 J.-H. Lin, J.S. Vitter, ε-approximations with minimum packing constraint violation, in: 24th ACM STOC, 1992, pp. 771–782 Muthukrishnan, 2005, Data streams: Algorithms and applications, Foundations Trends Theoret. Comput. Sci., 1, 10.1561/0400000002 F. Olken, Random sampling from databases, PhD thesis, Department of Computer Science, University of California at Berkeley, 1993 Rajan, 1989, An efficient parallel algorithm for random sampling, Inform. Process. Lett., 30, 265, 10.1016/0020-0190(89)90206-8 Vitter, 1984, Faster methods for random sampling, Comm. ACM, 27, 703, 10.1145/358105.893 Vitter, 1985, Random sampling with a reservoir, ACM Trans. Math. Software, 11, 37, 10.1145/3147.3165 Wong, 1980, An efficient method for weighted sampling without replacement, SIAM J. Comput., 9, 111, 10.1137/0209009