G. Cormode and D. Firmani. A unifying framework for l0-sampling algorithms. Distributed and Parallel Databases, 32(3):315-335, 2014. Special issue on Data Summarization on Big Data.

The problem of building an l0-sampler is to sample near-uniformly from the support set of a dynamic multiset. This problem has a variety of applications within data analysis, computational geometry and graph algorithms. In this paper, we abstract a set of steps for building an l0-sampler, based on sampling, recovery and selection. We analyze the implementation of an l0-sampler within this framework, and show how prior constructions of l0-samplers can all be expressed in terms of these steps. Our experimental contribution is to provide a first detailed study of the accuracy and computational cost of l0-samplers.

bib | Alternate Version | .pdf ] Back


This file was generated by bibtex2html 1.92.