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
- 11650
- Venue
- VLDB
- Year
- 2018
- Pagerank
- 7.8218804e-05
- Overall Rank
- 2,954 | 79.48%
- 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,899 |
VF2Boost: Very Fast Vertical Federated Gradient Boosting for Cross-Enterprise Learning |
2021 |
SIGMOD |
0.00010171063 |
| 2,918 |
DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees |
2019 |
VLDB |
7.9043213e-05 |
| 3,553 |
Approximate Selection with Guarantees using Proxies |
2020 |
VLDB |
6.9763548e-05 |
| 4,924 |
An Experimental Evaluation of Large Scale GBDT Systems |
2019 |
VLDB |
5.8211961e-05 |
| 7,340 |
Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries |
2021 |
SIGMOD |
4.7526052e-05 |
| 7,533 |
Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams |
2022 |
VLDB |
4.7134753e-05 |
| 8,669 |
CoopStore: Optimizing Precomputed Summaries for Aggregation |
2020 |
VLDB |
4.4667395e-05 |
| 8,715 |
Scotch: Generating FPGA-Accelerators for Sketching at Line Rate |
2021 |
VLDB |
4.4571724e-05 |
| 8,952 |
One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting |
2024 |
SIGMOD |
4.4195459e-05 |
| 9,002 |
Chasing Similarity: Distribution-aware Aggregation Scheduling |
2019 |
VLDB |
4.4077753e-05 |
| 9,230 |
Panakos: Chasing the Tails for Multidimensional Data Streams |
2023 |
VLDB |
4.3650857e-05 |
| 9,301 |
Controlled Intentional Degradation in Analytical Video Systems |
2022 |
SIGMOD |
4.3558097e-05 |
| 10,113 |
SplineSketch: Even More Accurate Quantiles with Error Guarantees |
2026 |
SIGMOD |
4.1905499e-05 |
| 10,986 |
A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions |
2024 |
SIGMOD |
4.1905499e-05 |
| 11,509 |
Approximating Median Absolute Deviation with Bounded Error |
2021 |
VLDB |
4.1905499e-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.0011695087 |
| 126 |
Space-Efficient Online Computation of Quantile Summaries |
2001 |
SIGMOD |
0.00044753012 |
| 324 |
Gigascope: A Stream Database for Network Applications |
2003 |
SIGMOD |
0.00027465124 |
| 398 |
Mergeable Summaries |
2012 |
PODS |
0.00024383201 |
| 461 |
SeeDB: Efficient Data-Driven Visualization Recommendations to Support Visual Analytics |
2015 |
VLDB |
0.00022615628 |
| 1,137 |
User-adaptive exploration of multidimensional data |
2000 |
VLDB |
0.0001373991 |
| 1,488 |
Scuba: Diving into Data at Facebook |
2013 |
VLDB |
0.00011690191 |
| 1,588 |
Druid: A Real-time Analytical Data Store |
2014 |
SIGMOD |
0.00011232949 |
| 2,129 |
MacroBase: Prioritizing Attention in Fast Data |
2017 |
SIGMOD |
9.4799835e-05 |
| 2,180 |
Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams |
2005 |
SIGMOD |
9.3629304e-05 |
| 3,387 |
Analytics in Motion: High Performance Event-Processing AND Real-Time Analytics in the Same Database |
2015 |
SIGMOD |
7.1505623e-05 |
| 3,878 |
Data Canopy: Accelerating Exploratory Statistical Analysis |
2017 |
SIGMOD |
6.6669911e-05 |
| 4,080 |
Quantiles over Data Streams: An Experimental Study |
2013 |
SIGMOD |
6.4619407e-05 |
| 5,177 |
User-Defined Aggregate Functions: Bridging Theory and Practice |
2006 |
SIGMOD |
5.6386942e-05 |
| 7,205 |
Kodiak: Leveraging Materialized Views For Very Low-Latency Analytics Over High-Dimensional Web-Scale Data |
2016 |
VLDB |
4.7965293e-05 |
| 7,329 |
Streaming in a Connected World: Querying and Tracking Distributed Data Streams |
2007 |
SIGMOD |
4.7559363e-05 |
Semantically Similar Papers