Back to papers
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
- 11649
- Venue
- VLDB
- Year
- 2018
- Pagerank
- 7.8267643e-05
- Overall Rank
- 2,953 | 79.46%
- DOI
-
10.14778/3236187.3236212
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 15 of 15 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 1,895 |
VF2Boost: Very Fast Vertical Federated Gradient Boosting for Cross-Enterprise Learning |
2021 |
SIGMOD |
0.00010180896 |
| 2,914 |
DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees |
2019 |
VLDB |
7.9118579e-05 |
| 3,558 |
Approximate Selection with Guarantees using Proxies |
2020 |
VLDB |
6.9765724e-05 |
| 4,975 |
An Experimental Evaluation of Large Scale GBDT Systems |
2019 |
VLDB |
5.79026e-05 |
| 7,358 |
Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries |
2021 |
SIGMOD |
4.7529363e-05 |
| 7,534 |
Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams |
2022 |
VLDB |
4.7180004e-05 |
| 8,673 |
CoopStore: Optimizing Precomputed Summaries for Aggregation |
2020 |
VLDB |
4.4709116e-05 |
| 8,717 |
Scotch: Generating FPGA-Accelerators for Sketching at Line Rate |
2021 |
VLDB |
4.4614498e-05 |
| 8,948 |
One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting |
2024 |
SIGMOD |
4.423786e-05 |
| 8,997 |
Chasing Similarity: Distribution-aware Aggregation Scheduling |
2019 |
VLDB |
4.4120041e-05 |
| 9,227 |
Panakos: Chasing the Tails for Multidimensional Data Streams |
2023 |
VLDB |
4.3692732e-05 |
| 9,296 |
Controlled Intentional Degradation in Analytical Video Systems |
2022 |
SIGMOD |
4.3599613e-05 |
| 10,113 |
SplineSketch: Even More Accurate Quantiles with Error Guarantees |
2026 |
SIGMOD |
4.1945683e-05 |
| 10,983 |
A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions |
2024 |
SIGMOD |
4.1945683e-05 |
| 11,505 |
Approximating Median Absolute Deviation with Bounded Error |
2021 |
VLDB |
4.1945683e-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.0011708144 |
| 126 |
Space-Efficient Online Computation of Quantile Summaries |
2001 |
SIGMOD |
0.00044744986 |
| 323 |
Gigascope: A Stream Database for Network Applications |
2003 |
SIGMOD |
0.00027492196 |
| 402 |
Mergeable Summaries |
2012 |
PODS |
0.00024196343 |
| 460 |
SeeDB: Efficient Data-Driven Visualization Recommendations to Support Visual Analytics |
2015 |
VLDB |
0.00022516069 |
| 1,137 |
User-adaptive exploration of multidimensional data |
2000 |
VLDB |
0.00013730532 |
| 1,487 |
Scuba: Diving into Data at Facebook |
2013 |
VLDB |
0.00011701099 |
| 1,588 |
Druid: A Real-time Analytical Data Store |
2014 |
SIGMOD |
0.00011239313 |
| 2,126 |
MacroBase: Prioritizing Attention in Fast Data |
2017 |
SIGMOD |
9.4887794e-05 |
| 2,178 |
Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams |
2005 |
SIGMOD |
9.3559565e-05 |
| 3,388 |
Analytics in Motion: High Performance Event-Processing AND Real-Time Analytics in the Same Database |
2015 |
SIGMOD |
7.1571148e-05 |
| 3,878 |
Data Canopy: Accelerating Exploratory Statistical Analysis |
2017 |
SIGMOD |
6.6731435e-05 |
| 4,076 |
Quantiles over Data Streams: An Experimental Study |
2013 |
SIGMOD |
6.4680854e-05 |
| 5,176 |
User-Defined Aggregate Functions: Bridging Theory and Practice |
2006 |
SIGMOD |
5.6439407e-05 |
| 7,207 |
Kodiak: Leveraging Materialized Views For Very Low-Latency Analytics Over High-Dimensional Web-Scale Data |
2016 |
VLDB |
4.800763e-05 |
| 7,334 |
Streaming in a Connected World: Querying and Tracking Distributed Data Streams |
2007 |
SIGMOD |
4.7604215e-05 |
Semantically Similar Papers