The Library
Quantiles over data streams : experimental comparisons, new analyses, and further improvements
Tools
Luo, Ge, Wang, Lu, Yi, Ke and Cormode, Graham (2016) Quantiles over data streams : experimental comparisons, new analyses, and further improvements. The VLDB Journal, 25 (4). pp. 449-472. doi:10.1007/s00778-016-0424-7 ISSN 1066-8888.
PDF
WRAP_1271140-cs-190816-nquantvldbj.pdf - Accepted Version - Requires a PDF viewer. Download (758Kb) |
Official URL: http://dx.doi.org/10.1007/s00778-016-0424-7
Abstract
A fundamental problem in data management and analysis is to generate descriptions of the distribution of data. It is most common to give such descriptions in terms of the cumulative distribution, which is characterized by the quantiles of the data. The design and engineering of efficient methods to find these quantiles has attracted much study, especially in the case where the data are given incrementally, and we must compute the quantiles in an online, streaming fashion. While such algorithms have proved to be extremely useful in practice, there has been limited formal comparison of the competing methods, and no comprehensive study of their performance. In this paper, we remedy this deficit by providing a taxonomy of different methods and describe efficient implementations. In doing so, we propose new variants that have not been studied before, yet which outperform existing methods. To illustrate this, we provide detailed experimental comparisons demonstrating the trade-offs between space, time, and accuracy for quantile computation.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > TK Electrical engineering. Electronics Nuclear engineering |
||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Algorithms, Streaming technology (Telecommunications) | ||||||
Journal or Publication Title: | The VLDB Journal | ||||||
Publisher: | Springer Berlin Heidelberg | ||||||
ISSN: | 1066-8888 | ||||||
Official Date: | 8 February 2016 | ||||||
Dates: |
|
||||||
Volume: | 25 | ||||||
Number: | 4 | ||||||
Page Range: | pp. 449-472 | ||||||
DOI: | 10.1007/s00778-016-0424-7 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 22 August 2016 | ||||||
Date of first compliant Open Access: | 8 February 2017 | ||||||
Funder: | European Research Council (ERC), Yahoo! Research Labs, Royal Society (Great Britain). Wolfson Research Merit Award (RSWRMA) | ||||||
Grant number: | ERC-2014-CoG 647557 (ERC) |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year