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.8494367e-05
Overall Rank
6,202 | 58.32%
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,295
ThalamusDB: Approximate Query Processing on Multi-Modal Data
2024
SIGMOD
8.6822982e-05
4,299
ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads
2024
VLDB
6.6766173e-05
6,686
Hierarchical Residual Encoding for Multiresolution Time Series Compression
2023
SIGMOD
5.7066636e-05
7,363
PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression
2024
VLDB
5.5404386e-05
7,518
Computing A Well-Representative Summary of Conjunctive Query Results
2024
PODS
5.5023404e-05
9,426
Towards Observability for Production Machine Learning Pipelines
2022
VLDB
5.1779092e-05
10,190
Saving Money for Analytical Workloads in the Cloud
2024
VLDB
5.0628015e-05
10,706
On Fair Epsilon Net and Geometric Hitting Set
2026
VLDB
4.9769913e-05
11,104
Smallest Synthetic Witnesses for Conjunctive Queries
2025
PODS
4.9769913e-05
11,193
FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network
2025
SIGMOD
4.9769913e-05
11,276
Approximation-First Timeseries Query At Scale
2025
VLDB
4.9769913e-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.00076265429
175
Simple Random Sampling from Relational Databases
1986
VLDB
0.00026776696
275
Optimal Histograms with Quality Guarantees
1998
VLDB
0.00022404363
318
DeepDB: Learn from Data, not from Queries!
2020
VLDB
0.00021166957
406
Deep Unsupervised Cardinality Estimation
2020
VLDB
0.00019050182
456
Mergeable Summaries
2012
PODS
0.00017904764
564
Congressional Samples for Approximate Answering of Group-By Queries
2000
SIGMOD
0.00016297598
666
Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure
2001
SIGMOD
0.00014989211
772
VerdictDB: Universalizing Approximate Query Processing
2018
SIGMOD
0.0001409096
795
Random Sampling over Joins Revisited
2018
SIGMOD
0.00013934719
841
Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters
2016
SIGMOD
0.00013543
930
Dynamic Sample Selection for Approximate Query Processing
2003
SIGMOD
0.00013009255
1,036
Fine-grained Partitioning for Aggressive Data Skipping
2014
SIGMOD
0.00012372946
1,061
Approximate Query Processing: No Silver Bullet
2017
SIGMOD
0.00012208639
1,182
ICICLES: Self-tuning Samples for Approximate Query Answering
2000
VLDB
0.00011615497
1,687
Global Optimization of Histograms
2001
SIGMOD
9.8614576e-05
1,722
A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data
2014
SIGMOD
9.7921604e-05
2,003
Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee
2016
SIGMOD
9.2071735e-05
2,028
Database Learning: Toward a Database that Becomes Smarter Every Time
2017
SIGMOD
9.1584244e-05
2,654
A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries
2001
SIGMOD
8.1670397e-05
3,417
Revisiting Reuse for Approximate Query Processing
2017
VLDB
7.3184905e-05
3,424
AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics
2018
SIGMOD
7.3084429e-05
3,646
Optimal Histograms for Hierarchical Range Queries (Extended Abstract)
2000
PODS
7.1368554e-05
6,786
Robust Estimation With Sampling and Approximate Pre-Aggregation
2003
VLDB
5.6811262e-05
7,152
Learning to Sample: Counting with Complex Queries
2020
VLDB
5.5959861e-05
8,172
Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints
2020
SIGMOD
5.3824434e-05
8,289
Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters
2019
VLDB
5.360349e-05
8,783
CoopStore: Optimizing Precomputed Summaries for Aggregation
2020
VLDB
5.2776273e-05
8,876
Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views
2015
VLDB
5.2587627e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
3,756
Accelerating Approximate Aggregation Queries with Expensive Predicates
2021
VLDB
2
2,654
A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries
2001
SIGMOD
3
930
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
11,800
Approximate Queries over Concurrent Updates
2023
VLDB
6
10,555
Approximate Query Processing under Updates
2026
SIGMOD
7
3,424
AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics
2018
SIGMOD
8
5,829
Joins on Samples: A Theoretical Guide for Practitioners
2020
VLDB
9
11,088
Efficient Approximate Query Processing with Block Sampling
2025
CIDR
10
2,003
Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee
2016
SIGMOD