Logging every footstep: Quantile summaries for the entire history
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
AbstractQuantiles are a crucial type of order statistics in databases. Extensive research has been focused on maintaining a space-efficient structure for approximate quantile computation as the underlying dataset is updated. The existing solutions, however, are designed to support only the current, most-updated, snapshot of the dataset. Queries on the past versions of the data cannot be answered. This paper studies the problem of historical quantile search. The objective is to enable ε-approximate quantile retrieval on any snapshot of the dataset in history. The problem is very important in analyzing the evolution of a distribution, monitoring the quality of services, query optimization in temporal databases, and so on. We present the first formal results in the literature. First, we prove a novel theoretical lower bound on the space cost of supporting ε-approximate historical quantile queries. The bound reveals the fundamental difference between answering quantile queries about the past and those about the present time. Second, we propose a structure for finding ε-approximate historical quantiles, and show that it consumes more space than the lower bound by only a square-logarithmic factor. Extensive experiments demonstrate that in practice our technique performs much better than predicted by theory. In particular, the quantiles it returns are remarkably more accurate than the theoretical precision guarantee. © 2010 ACM.
All Author(s) ListTao Y., Yi K., Sheng C., Pei J., Li F.
Name of Conference2010 International Conference on Management of Data, SIGMOD '10
Start Date of Conference06/06/2010
End Date of Conference11/06/2010
Place of ConferenceIndianapolis, IN
Country/Region of ConferenceUnited States of America
Detailed descriptionorganized by ACM,
Pages639 - 650
LanguagesEnglish-United Kingdom
Keywordsapproximation, lower bound, quantile

Last updated on 2021-24-02 at 00:35