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
6230
Venue
SIGMOD
Year
2021
Pagerank
5.9443409e-05
Overall Rank
6,206 | 57.43%
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
3,684
ThalamusDB: Approximate Query Processing on Multi-Modal Data
2024
SIGMOD
7.2033959e-05
4,349
ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads
2024
VLDB
6.7504619e-05
6,556
Hierarchical Residual Encoding for Multiresolution Time Series Compression
2023
SIGMOD
5.8404094e-05
7,351
PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression
2024
VLDB
5.6354898e-05
8,728
Computing A Well-Representative Summary of Conjunctive Query Results
2024
PODS
5.3766157e-05
9,245
Towards Observability for Production Machine Learning Pipelines
2022
VLDB
5.2992628e-05
10,000
Saving Money for Analytical Workloads in the Cloud
2024
VLDB
5.1814573e-05
10,511
On Fair Epsilon Net and Geometric Hitting Set
2026
VLDB
5.093636e-05
10,652
Smallest Synthetic Witnesses for Conjunctive Queries
2025
PODS
5.093636e-05
10,760
FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network
2025
SIGMOD
5.093636e-05
10,865
Approximation-First Timeseries Query At Scale
2025
VLDB
5.093636e-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.00077458002
173
Simple Random Sampling from Relational Databases
1986
VLDB
0.00027273858
267
Optimal Histograms with Quality Guarantees
1998
VLDB
0.00022798161
323
DeepDB: Learn from Data, not from Queries!
2020
VLDB
0.00021264788
401
Deep Unsupervised Cardinality Estimation
2020
VLDB
0.00019092557
451
Mergeable Summaries
2012
PODS
0.00018151445
553
Congressional Samples for Approximate Answering of Group-By Queries
2000
SIGMOD
0.00016590619
648
Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure
2001
SIGMOD
0.00015324657
772
VerdictDB: Universalizing Approximate Query Processing
2018
SIGMOD
0.00014147905
802
Random Sampling over Joins Revisited
2018
SIGMOD
0.00013907725
819
Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters
2016
SIGMOD
0.00013815639
909
Dynamic Sample Selection for Approximate Query Processing
2003
SIGMOD
0.00013291205
1,044
Fine-grained Partitioning for Aggressive Data Skipping
2014
SIGMOD
0.0001244236
1,108
Approximate Query Processing: No Silver Bullet
2017
SIGMOD
0.00012145154
1,166
ICICLES: Self-tuning Samples for Approximate Query Answering
2000
VLDB
0.00011850439
1,668
Global Optimization of Histograms
2001
SIGMOD
0.00010057026
1,736
A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data
2014
SIGMOD
9.8984415e-05
1,962
Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee
2016
SIGMOD
9.3978414e-05
1,995
Database Learning: Toward a Database that Becomes Smarter Every Time
2017
SIGMOD
9.3403665e-05
2,608
A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries
2001
SIGMOD
8.347674e-05
3,366
AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics
2018
SIGMOD
7.4748604e-05
3,370
Revisiting Reuse for Approximate Query Processing
2017
VLDB
7.4700891e-05
3,575
Optimal Histograms for Hierarchical Range Queries (Extended Abstract)
2000
PODS
7.2946291e-05
6,654
Robust Estimation With Sampling and Approximate Pre-Aggregation
2003
VLDB
5.8131331e-05
7,048
Learning to Sample: Counting with Complex Queries
2020
VLDB
5.7178054e-05
8,002
Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints
2020
SIGMOD
5.5085906e-05
8,108
Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters
2019
VLDB
5.4850569e-05
8,616
CoopStore: Optimizing Precomputed Summaries for Aggregation
2020
VLDB
5.4004741e-05
8,714
Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views
2015
VLDB
5.3778009e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
7,419
Structure-Aware Sampling: Flexible and Accurate Summarization
2011
VLDB
2
2,608
A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries
2001
SIGMOD
3
909
Dynamic Sample Selection for Approximate Query Processing
2003
SIGMOD
4
1,401
Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems
2014
SIGMOD
5
11,484
Approximate Queries over Concurrent Updates
2023
VLDB
6
10,342
Approximate Query Processing under Updates
2026
SIGMOD
7
3,366
AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics
2018
SIGMOD
8
5,743
Joins on Samples: A Theoretical Guide for Practitioners
2020
VLDB
9
10,634
Efficient Approximate Query Processing with Block Sampling
2025
CIDR
10
1,962
Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee
2016
SIGMOD