The notion of Lp sampling, and corresponding algorithms known as Lp samplers, have found a wide range of applications in the design of data stream algorithms and beyond. In this survey we present some of the core algorithms to achieve this sampling distribution based on ideas from hashing, sampling and sketching. We give results for the special cases of insertion-only inputs, lower bounds for the sampling problems, and ways to efficiently sample multiple elements. We describe a range of applications of Lp drawing on problems across the domain of computer science, from matrix and graph computations, as well as to geometric and vector streaming problems.
[ bib | .pdf ] Back
This file was generated by bibtex2html 1.92.