Back to papers
Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing
Summary: Introduces PASS, Precomputation-Assisted Stratified Sampling: a partitioned tree of partial aggregates to speed up AQP. Exact answers for partition-aligned predicates via DFS; partial overlaps are approximated by stratified samples with an algorithm for near-optimal partitioning.
(summarized by gpt-5-nano on Feb 09 2026)
Paper ID
h57bba2383b49ed7e
Venue
SIGMOD
Year
2021
Pagerank
5.8463347e-05
Overall Rank
6,221 | 58.18%
DOI
10.1145/3448016.3457277
Incoming Non-self Citations Over Time
BibTeX Citation
Copy BibTeX
@inproceedings{liang_sigmod21,
title = {{Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing}},
author = {Liang, Xi and Sintos, Stavros and Shang, Zechao and Krishnan, Sanjay},
series = {{SIGMOD} '21},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3448016.3457277},
url = {https://dl.acm.org/doi/10.1145/3448016.3457277},
year = {2021}
}
Incoming Citations (Sorted by Pagerank)
Showing 11 of 11 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
2,450
ThalamusDB: Approximate Query Processing on Multi-Modal Data
2024
SIGMOD
8.4474092e-05
4,311
ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads
2024
VLDB
6.6727978e-05
6,682
Hierarchical Residual Encoding for Multiresolution Time Series Compression
2023
SIGMOD
5.7093663e-05
7,375
PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression
2024
VLDB
5.5400509e-05
7,513
Computing A Well-Representative Summary of Conjunctive Query Results
2024
PODS
5.5049463e-05
9,417
Towards Observability for Production Machine Learning Pipelines
2022
VLDB
5.1803615e-05
10,187
Saving Money for Analytical Workloads in the Cloud
2024
VLDB
5.0651993e-05
10,696
On Fair Epsilon Net and Geometric Hitting Set
2026
VLDB
4.9793485e-05
11,095
Smallest Synthetic Witnesses for Conjunctive Queries
2025
PODS
4.9793485e-05
11,184
FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network
2025
SIGMOD
4.9793485e-05
11,268
Approximation-First Timeseries Query At Scale
2025
VLDB
4.9793485e-05
Outgoing Citations (Sorted by Pagerank)
Showing 29 of 29 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Rank
Cited Paper
Year
Venue
Pagerank
9
Online Aggregation
1997
SIGMOD
0.00076195956
175
Simple Random Sampling from Relational Databases
1986
VLDB
0.00026784195
275
Optimal Histograms with Quality Guarantees
1998
VLDB
0.00022413521
318
DeepDB: Learn from Data, not from Queries!
2020
VLDB
0.00021167555
406
Deep Unsupervised Cardinality Estimation
2020
VLDB
0.00019045544
456
Mergeable Summaries
2012
PODS
0.0001791284
564
Congressional Samples for Approximate Answering of Group-By Queries
2000
SIGMOD
0.00016296665
664
Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure
2001
SIGMOD
0.00014995058
784
VerdictDB: Universalizing Approximate Query Processing
2018
SIGMOD
0.00014012614
795
Random Sampling over Joins Revisited
2018
SIGMOD
0.00013938779
840
Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters
2016
SIGMOD
0.0001354605
931
Dynamic Sample Selection for Approximate Query Processing
2003
SIGMOD
0.00013011667
1,036
Fine-grained Partitioning for Aggressive Data Skipping
2014
SIGMOD
0.00012377471
1,082
Approximate Query Processing: No Silver Bullet
2017
SIGMOD
0.00012122749
1,183
ICICLES: Self-tuning Samples for Approximate Query Answering
2000
VLDB
0.00011616705
1,687
Global Optimization of Histograms
2001
SIGMOD
9.8655879e-05
1,720
A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data
2014
SIGMOD
9.7965659e-05
2,000
Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee
2016
SIGMOD
9.2112617e-05
2,027
Database Learning: Toward a Database that Becomes Smarter Every Time
2017
SIGMOD
9.1618139e-05
2,655
A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries
2001
SIGMOD
8.1706092e-05
3,419
Revisiting Reuse for Approximate Query Processing
2017
VLDB
7.3190065e-05
3,424
AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics
2018
SIGMOD
7.3117029e-05
3,644
Optimal Histograms for Hierarchical Range Queries (Extended Abstract)
2000
PODS
7.1399991e-05
6,781
Robust Estimation With Sampling and Approximate Pre-Aggregation
2003
VLDB
5.6836871e-05
7,166
Learning to Sample: Counting with Complex Queries
2020
VLDB
5.5949741e-05
8,166
Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints
2020
SIGMOD
5.3849926e-05
8,283
Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters
2019
VLDB
5.3627138e-05
8,776
CoopStore: Optimizing Precomputed Summaries for Aggregation
2020
VLDB
5.2800094e-05
8,870
Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views
2015
VLDB
5.2601766e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
7,557
Structure-Aware Sampling: Flexible and Accurate Summarization
2011
VLDB
2
2,655
A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries
2001
SIGMOD
3
931
Dynamic Sample Selection for Approximate Query Processing
2003
SIGMOD
4
1,428
Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems
2014
SIGMOD
5
10,544
Approximate Query Processing under Updates
2026
SIGMOD
6
11,794
Approximate Queries over Concurrent Updates
2023
VLDB
7
3,424
AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics
2018
SIGMOD
8
5,831
Joins on Samples: A Theoretical Guide for Practitioners
2020
VLDB
9
11,079
Efficient Approximate Query Processing with Block Sampling
2025
CIDR
10
2,000
Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee
2016
SIGMOD