The Library
Lp samplers and their applications : a survey
Tools
Cormode, Graham and Jowhari, Hossein (2019) Lp samplers and their applications : a survey. ACM Computing Surveys, 52 (1). 16. doi:10.1145/3297715 ISSN 0360-0300.
|
PDF
WRAP-lp-samplers-their-applications-Cormode-2018.pdf - Accepted Version - Requires a PDF viewer. Download (1953Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/3297715
Abstract
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.
Item Type: | Journal Article | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||
Library of Congress Subject Headings (LCSH): | Algorithms, Sampling (Statistics) | ||||||||||||
Journal or Publication Title: | ACM Computing Surveys | ||||||||||||
Publisher: | Association for Computing Machinery | ||||||||||||
ISSN: | 0360-0300 | ||||||||||||
Official Date: | 1 February 2019 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 52 | ||||||||||||
Number: | 1 | ||||||||||||
Article Number: | 16 | ||||||||||||
DOI: | 10.1145/3297715 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Reuse Statement (publisher, data, author rights): | This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Computing Surveys: http://dx.doi.org/10.1145/3297715 | ||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
Date of first compliant deposit: | 17 December 2018 | ||||||||||||
Date of first compliant Open Access: | 29 April 2019 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year