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.
![[thumbnail of WRAP-Relative-error-streaming-quantiles-23.pdf]](https://cdn.statically.io/img/wrap.warwick.ac.uk/180761/2.hassmallThumbnailVersion/WRAP-Relative-error-streaming-quantiles-23.pdf)  Preview |
PDF
WRAP-Relative-error-streaming-quantiles-23.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (741kB) | Preview |
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: | Date Event 16 October 2023 Published 26 August 2023 Accepted |
| 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 open licence) |
| Date of first compliant deposit: | 6 November 2023 |
| Date of first compliant Open Access: | 8 November 2023 |
| RIOXX Funder/Project Grant: | Project/Grant ID RIOXX Funder Name Funder ID 19-27871X Grantová Agentura České Republiky UNSPECIFIED |
| Persistent URL: | https://wrap.warwick.ac.uk/180761/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |