Moment-based quantile sketches for efficient high cardinality aggregation queries
Authors:
Open Access
- 1 July 2018
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 11 (11) , 1647-1660
Abstract
Interactive analytics increasingly involves querying for quantiles over sub-populations of high cardinality datasets. Data processing engines such as Druid and Spark use mergeable summaries to estimate quantiles, but summary merge times can be a bottleneck during aggregation. We show how a compact and efficiently mergeable quantile sketch can support aggregation workloads. This data structure, which we refer to as the moments sketch, operates with a small memory footprint (200 bytes) and computationally efficient (50ns) merges by tracking only a set of summary statistics, notably the sample moments. We demonstrate how we can efficiently estimate quantiles using the method of moments and the maximum entropy principle, and show how the use of a cascade further improves query time for threshold predicates. Empirical evaluation shows that the moments sketch can achieve less than 1 percent quantile error with 15× less overhead than comparable summaries, improving end query time in the MacroBase engine by up to 7× and the Druid engine by up to 60×.Keywords
All Related Versions
This publication has 56 references indexed in Scilit:
- Synopses for Massive Data: Samples, Histograms, Wavelets, SketchesFoundations and Trends® in Databases, 2011
- Quantiles on Streams2009
- Consistent selectivity estimation via maximum entropyThe VLDB Journal, 2006
- Data Streams: Algorithms and ApplicationsFoundations and Trends® in Theoretical Computer Science, 2005
- Maximum entropy and the problem of moments: A stable algorithmPhysical Review E, 2005
- Space-efficient online computation of quantile summariesACM SIGMOD Record, 2001
- Calculation of densities of states and spectral functions by Chebyshev recursion and maximum entropyPhysical Review E, 1997
- Implementing data cubes efficientlyACM SIGMOD Record, 1996
- Random sampling with a reservoirACM Transactions on Mathematical Software, 1985
- Information Theory and Statistical MechanicsPhysical Review B, 1957