The Library
Relative error streaming quantiles
Tools
Cormode, Graham, Karnin, Zohar, Liberty, Edo, Thaler, Justin and Veselý, Pavel (2023) Relative error streaming quantiles. Journal of the ACM, 70 (5). pp. 1-48. doi:10.1145/3617891 ISSN 0004-5411.
|
PDF
WRAP-Relative-error-streaming-quantiles-23.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (724Kb) | Preview |
Official URL: http://doi.org/10.1145/3617891
Abstract
Estimating ranks, quantiles, and distributions over streaming data is a central task in data analysis and monitoring. Given a stream of n items from a data universe equipped with a total order, the task is to compute a sketch (data structure) of size polylogarithmic in n. Given the sketch and a query item y, one should be able to approximate its rank in the stream, i.e., the number of stream elements smaller than or equal to y.
Item Type: | Journal Article | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Data structures (Computer science) , Database management , Algorithms , Computer networks -- Management -- Algorithms, Quantile regression | ||||||||||||||||||
Journal or Publication Title: | Journal of the ACM | ||||||||||||||||||
Publisher: | Association for Computing Machinery, Inc. | ||||||||||||||||||
ISSN: | 0004-5411 | ||||||||||||||||||
Official Date: | 16 October 2023 | ||||||||||||||||||
Dates: |
|
||||||||||||||||||
Volume: | 70 | ||||||||||||||||||
Number: | 5 | ||||||||||||||||||
Page Range: | pp. 1-48 | ||||||||||||||||||
DOI: | 10.1145/3617891 | ||||||||||||||||||
Status: | Peer Reviewed | ||||||||||||||||||
Publication Status: | Published | ||||||||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||||||||
Date of first compliant deposit: | 6 November 2023 | ||||||||||||||||||
Date of first compliant Open Access: | 8 November 2023 | ||||||||||||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year