The problem of building an l0-sampler is to sample nearuniformly 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.

Cormode, G., Firmani, D. (2013). On unifying the space of l0-sampling algorithms. In 15th Workshop on Algorithm Engineering and Experiments (ALENEX) (pp.163-172). Society for Industrial and Applied Mathematics Publications [10.1137/1.9781611972931.14].

On unifying the space of l0-sampling algorithms

Firmani Donatella
2013-01-01

Abstract

The problem of building an l0-sampler is to sample nearuniformly 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.
2013
978-1-61197-253-5
Cormode, G., Firmani, D. (2013). On unifying the space of l0-sampling algorithms. In 15th Workshop on Algorithm Engineering and Experiments (ALENEX) (pp.163-172). Society for Industrial and Applied Mathematics Publications [10.1137/1.9781611972931.14].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/368664
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact