The Library
A unifying framework for ℓ 0-sampling algorithms
Tools
Cormode, Graham and Firmani, Donatella (2014) A unifying framework for ℓ 0-sampling algorithms. Distributed and Parallel Databases, Volume 32 (Number 3). pp. 315-335. doi:10.1007/s10619-013-7131-9 ISSN 0926-8782.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/s10619-013-7131-9
Abstract
The problem of building an ℓ 0-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 ℓ 0-sampler, based on sampling, recovery and selection. We analyze the implementation of an ℓ 0-sampler within this framework, and show how prior constructions of ℓ 0-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 ℓ 0-samplers.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Journal or Publication Title: | Distributed and Parallel Databases | ||||||
Publisher: | Springer New York LLC | ||||||
ISSN: | 0926-8782 | ||||||
Official Date: | September 2014 | ||||||
Dates: |
|
||||||
Volume: | Volume 32 | ||||||
Number: | Number 3 | ||||||
Page Range: | pp. 315-335 | ||||||
DOI: | 10.1007/s10619-013-7131-9 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Embodied As: | 1 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |