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: 8.1273838e-05
Overall Rank: 2,675 | 82.08%
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 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,020	VF2Boost: Very Fast Vertical Federated Gradient Boosting for Cross-Enterprise Learning	2021	SIGMOD	9.1641863e-05
2,332	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB	8.614375e-05
2,777	Approximate Selection with Guarantees using Proxies	2020	VLDB	8.0101016e-05
5,738	An Experimental Evaluation of Large Scale GBDT Systems	2019	VLDB	5.9951855e-05
7,387	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.5212177e-05
7,720	Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams	2022	VLDB	5.4542911e-05
8,574	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.297131e-05
8,800	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	5.2602992e-05
8,837	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	5.2523304e-05
9,027	Scotch: Generating FPGA-Accelerators for Sketching at Line Rate	2021	VLDB	5.2200134e-05
9,176	One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting	2024	SIGMOD	5.200391e-05
9,249	Chasing Similarity: Distribution-aware Aggregation Scheduling	2019	VLDB	5.1860134e-05
9,574	Controlled Intentional Degradation in Analytical Video Systems	2022	SIGMOD	5.1428165e-05
10,403	Near-Optimal Per-Key Streaming Quantile Estimation	2027	SIGMOD	4.9605343e-05
11,593	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.9605343e-05
12,057	Approximating Median Absolute Deviation with Bounded Error	2021	VLDB	4.9605343e-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.00070860346
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036097627
240	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023371986
395	SeeDB: Efficient Data-Driven Visualization Recommendations to Support Visual Analytics	2015	VLDB	0.00019125046
452	Mergeable Summaries	2012	PODS	0.00018032092
986	User-adaptive exploration of multidimensional data	2000	VLDB	0.00012645438
1,240	Druid: A Real-time Analytical Data Store	2014	SIGMOD	0.00011373933
1,379	Scuba: Diving into Data at Facebook	2013	VLDB	0.00010836332
1,844	MacroBase: Prioritizing Attention in Fast Data	2017	SIGMOD	9.5112726e-05
2,130	Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams	2005	SIGMOD	8.9875498e-05
3,127	Analytics in Motion: High Performance Event-Processing AND Real-Time Analytics in the Same Database	2015	SIGMOD	7.6047902e-05
3,667	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.0967962e-05
3,993	Data Canopy: Accelerating Exploratory Statistical Analysis	2017	SIGMOD	6.8565106e-05
5,028	User-Defined Aggregate Functions: Bridging Theory and Practice	2006	SIGMOD	6.2956973e-05
7,366	Kodiak: Leveraging Materialized Views For Very Low-Latency Analytics Over High-Dimensional Web-Scale Data	2016	VLDB	5.5268158e-05
7,435	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	5.5132769e-05

Semantically Similar Papers

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