Space-efficient online computation of quantile summaries

By Michael B. Greenwald, Sanjeev Khanna. 2001

622 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Algorithms & Complexity, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Algorithms & Complexity

In Signal Processing

Citations in the corpus

8-bit Optimizers via Block-wise Quantization (2021, methodology): “Greenwald and Khanna (2001)’s quantile estimation algorithm uses dynamic bin histograms over sliding windows to estimate quantiles.”
XGBoost: A Scalable Tree Boosting System (2016, methodology): “One classical approach to this problem is GK algorithm [14] and extensions based on the GK framework [24].”
Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams (2009, methodology): “Quantile estimation is perhaps the most extensively studied problem in the data-stream model [3,4,9,10,15,19,20,23].”
Plato (2020, neutral): “Approximately answering queries while providing deterministic error guarantees has been successfully applied in many applications [13, 23, 40, 51, 36, 50].”
Medians and beyond: new aggregation techniques for sensor networks (2004, methodology): “Consider a set of n = 15 values in the range [1, 8] as shown in Fig.”
Learning Feature Engineering for Classification (2017, methodology): “Quantile has been used as a ﬁxed-size space representation and achieves reasonably accurate approximation to the distribution function induced by the data being sketched [Greenwald and Khanna, 2001].”
Approximate join processing over data streams (2003, methodology): “For maintaining online data stream statistics, e.g., in order to compute the tuple priorities for join memory replacement, some of the recently proposed stream aggregation approaches could be applied. Recent work includes [10, 12, 14 , 15, 27].”
Approximate counts and quantiles over sliding windows (2004, methodology): “, 1〉, though the lemma is valid for the more general class of sketches introduced in [15].”
Fast and approximate stream mining of quantiles and frequencies using graphics processors (2005, methodology): “Entire past history: Apply the query over all the elements in the past history of the stream [12, 22, 23, 27, 28, 34].”
Automating Large-Scale Data Quality Verification (2018, methodology): “ApproxQuantile approximate quantile of the value in a column [15]”
Data Streams: Models and Algorithms (Advances in Database Systems) (2006, neutral): “[17] Jain A., Dubes R. (1998). Algorithms for Clustering Data, Prentice Hall, New Jersey.”
Quantitative Data Cleaning for Large Databases (2008, methodology): “The two most-cited algorithms [Manku et al., 1998, Greenwald and Khanna, 2001] differ slightly in their implementation and guarantees, but share the same general approach.”
Efficient Computation of Frequent and Top-k Elements in Data Streams (2005, background): “Problems studied in this context include approximate frequency moments [1], differences [20], distinct values estimation [22, 33, 45], bit counting [16], duplicate detection [42], approximate quantiles [28, 38, 40], histograms [30, 29], wavelet based aggregate queries [25, 41], correlated aggregate ”
Continuous queries over data streams (2001, neutral): “The problem of computing approximate quantiles (equi-height histograms) over numeric data streams of unknown length is addressed in [MRL99] and [ GK01 ].”
An improved data stream summary: the count-min sketch and its applications (2004, methodology): “One way to compute approximate range sums is via approximate quantiles: use an algorithm such as [25,22] to find the quantiles of the stream, and then count how many quantiles fall within the range of interest to give an O(ε) approximation of the range query.”