Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries

Understand

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.