Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries
Authors:
Preprint
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 and practically 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 on real-world datasets shows that the moments sketch can achieve less than 1 percent error with 15 times less merge overhead than comparable summaries, improving end query time in the MacroBase engine by up to 7 times and the Druid engine by up to 60 times.Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- Quantiles over data streams: experimental comparisons, new analyses, and further improvementsThe VLDB Journal, 2016
- Hausdorff moment problem: Reconstruction of distributionsStatistics & Probability Letters, 2008
- A moments based distribution bounding methodMathematical and Computer Modelling, 2006
- Maximum entropy and the problem of moments: A stable algorithmPhysical Review E, 2005
- An improved data stream summary: the count-min sketch and its applicationsJournal of Algorithms, 2005
- Calculation of densities of states and spectral functions by Chebyshev recursion and maximum entropyPhysical Review E, 1997
- Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-TotalsData Mining and Knowledge Discovery, 1997
- On the limited memory BFGS method for large scale optimizationMathematical Programming, 1989
- Maximum entropy in the problem of momentsJournal of Mathematical Physics, 1984
- Information Theory and Statistical MechanicsPhysical Review B, 1957