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: 11837
Venue: VLDB
Year: 2018
Pagerank: 8.1711208e-05
Overall Rank: 2,747 | 81.16%
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
1,959	VF2Boost: Very Fast Vertical Federated Gradient Boosting for Cross-Enterprise Learning	2021	SIGMOD	9.4090198e-05
2,455	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB	8.5552968e-05
2,898	Approximate Selection with Guarantees using Proxies	2020	VLDB	7.978725e-05
5,589	An Experimental Evaluation of Large Scale GBDT Systems	2019	VLDB	6.1559057e-05
7,256	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.6625146e-05
7,551	Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams	2022	VLDB	5.6006414e-05
8,616	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	5.4004741e-05
8,878	Scotch: Generating FPGA-Accelerators for Sketching at Line Rate	2021	VLDB	5.3532614e-05
8,986	One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting	2024	SIGMOD	5.3387783e-05
9,100	Chasing Similarity: Distribution-aware Aggregation Scheduling	2019	VLDB	5.3250075e-05
9,329	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.2894515e-05
9,406	Controlled Intentional Degradation in Analytical Video Systems	2022	SIGMOD	5.2751448e-05
9,618	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	5.2434488e-05
11,196	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	5.093636e-05
11,703	Approximating Median Absolute Deviation with Bounded Error	2021	VLDB	5.093636e-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.00071822821
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
230	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023891474
410	SeeDB: Efficient Data-Driven Visualization Recommendations to Support Visual Analytics	2015	VLDB	0.0001890421
451	Mergeable Summaries	2012	PODS	0.00018151445
965	User-adaptive exploration of multidimensional data	2000	VLDB	0.00012933878
1,242	Druid: A Real-time Analytical Data Store	2014	SIGMOD	0.00011516162
1,352	Scuba: Diving into Data at Facebook	2013	VLDB	0.00011064595
1,792	MacroBase: Prioritizing Attention in Fast Data	2017	SIGMOD	9.7436856e-05
2,090	Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams	2005	SIGMOD	9.1894752e-05
3,082	Analytics in Motion: High Performance Event-Processing AND Real-Time Analytics in the Same Database	2015	SIGMOD	7.7725834e-05
3,765	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.1442477e-05
3,930	Data Canopy: Accelerating Exploratory Statistical Analysis	2017	SIGMOD	7.0102082e-05
4,896	User-Defined Aggregate Functions: Bridging Theory and Practice	2006	SIGMOD	6.4548696e-05
7,238	Kodiak: Leveraging Materialized Views For Very Low-Latency Analytics Over High-Dimensional Web-Scale Data	2016	VLDB	5.664642e-05
7,284	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	5.6560822e-05

Semantically Similar Papers

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