Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries

Summary: Moment-based quantile sketch for mergeable, high-cardinality aggregations; 200-byte footprint and 50ns merges by tracking a compact set of moments, with estimation via method of moments and maximum entropy. Cascade boost for threshold predicates; <1% quantile error, ~15× lower overhead than alternatives, and end-to-end speedups up to 7× (MacroBase) and 60× (Druid). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h473e1cfe162fb7d4
Venue: VLDB
Year: 2018
Pagerank: 7.9933329e-05
Overall Rank: 2,798 | 81.19%
DOI: 10.14778/3236187.3236212

Incoming Non-self Citations Over Time

Authors

1. Edward Gan (Stanford University)
2. Jialin Ding (Stanford University)
3. Kai Sheng Tai (Stanford University)
4. Vatsal Sharan (Stanford University)
5. Peter Bailis (Stanford University)

BibTeX Citation

@article{gan_vldb18,
        title = {{Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries}},
        author = {Gan, Edward and Ding, Jialin and Tai, Kai Sheng and Sharan, Vatsal and Bailis, Peter},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {11},
        pages = {1647--1660},
        doi = {10.14778/3236187.3236212},
        url = {https://doi.org/10.14778/3236187.3236212},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,007	VF2Boost: Very Fast Vertical Federated Gradient Boosting for Cross-Enterprise Learning	2021	SIGMOD	9.198944e-05
2,432	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB	8.4766851e-05
2,776	Approximate Selection with Guarantees using Proxies	2020	VLDB	8.0309448e-05
5,723	An Experimental Evaluation of Large Scale GBDT Systems	2019	VLDB	6.0178515e-05
7,364	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.5418075e-05
7,701	Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams	2022	VLDB	5.474978e-05
8,776	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	5.2800094e-05
9,039	Scotch: Generating FPGA-Accelerators for Sketching at Line Rate	2021	VLDB	5.2331548e-05
9,145	One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting	2024	SIGMOD	5.220115e-05
9,215	Chasing Similarity: Distribution-aware Aggregation Scheduling	2019	VLDB	5.2056826e-05
9,509	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.1707704e-05
9,539	Controlled Intentional Degradation in Analytical Video Systems	2022	SIGMOD	5.1621607e-05
9,798	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	5.1257999e-05
11,538	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.9793485e-05
12,007	Approximating Median Absolute Deviation with Bounded Error	2021	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
11	Implementing Data Cubes Efficiently	1996	SIGMOD	0.00071084324
83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00035978046
240	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023435436
395	SeeDB: Efficient Data-Driven Visualization Recommendations to Support Visual Analytics	2015	VLDB	0.00019165452
456	Mergeable Summaries	2012	PODS	0.0001791284
984	User-adaptive exploration of multidimensional data	2000	VLDB	0.00012686375
1,236	Druid: A Real-time Analytical Data Store	2014	SIGMOD	0.00011402848
1,381	Scuba: Diving into Data at Facebook	2013	VLDB	0.00010860462
1,833	MacroBase: Prioritizing Attention in Fast Data	2017	SIGMOD	9.5405247e-05
2,124	Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams	2005	SIGMOD	9.0056375e-05
3,122	Analytics in Motion: High Performance Event-Processing AND Real-Time Analytics in the Same Database	2015	SIGMOD	7.6236292e-05
3,678	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.104636e-05
3,984	Data Canopy: Accelerating Exploratory Statistical Analysis	2017	SIGMOD	6.8741188e-05
5,012	User-Defined Aggregate Functions: Bridging Theory and Practice	2006	SIGMOD	6.3145331e-05
7,360	Kodiak: Leveraging Materialized Views For Very Low-Latency Analytics Over High-Dimensional Web-Scale Data	2016	VLDB	5.5427171e-05
7,431	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	5.5293382e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,116	Randomized Sketches for Quantile in LSM-tree based Store	2025	SIGMOD
2	9,798	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD
3	8,104	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD
4	83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD
5	3,678	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD
6	8,170	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD
7	2,432	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB
8	10,674	Quantile Estimation with Duplicates	2026	SIGMOD
9	9,496	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB
10	9,570	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD