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.8362492e-05
Overall Rank
6,198 | 58.46%
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,225
ThalamusDB: Approximate Query Processing on Multi-Modal Data
2024
SIGMOD
8.7996555e-05
4,315
ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads
2024
VLDB
6.6545412e-05
6,700
Hierarchical Residual Encoding for Multiresolution Time Series Compression
2023
SIGMOD
5.6877938e-05
7,365
PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression
2024
VLDB
5.5273291e-05
7,537
Computing A Well-Representative Summary of Conjunctive Query Results
2024
PODS
5.4841462e-05
9,454
Towards Observability for Production Machine Learning Pipelines
2022
VLDB
5.1607878e-05
9,476
Saving Money for Analytical Workloads in the Cloud
2024
VLDB
5.157794e-05
10,767
On Fair Epsilon Net and Geometric Hitting Set
2026
VLDB
4.9605343e-05
11,165
Smallest Synthetic Witnesses for Conjunctive Queries
2025
PODS
4.9605343e-05
11,252
FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network
2025
SIGMOD
4.9605343e-05
11,332
Approximation-First Timeseries Query At Scale
2025
VLDB
4.9605343e-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.00076079812
175
Simple Random Sampling from Relational Databases
1986
VLDB
0.00026701703
277
Optimal Histograms with Quality Guarantees
1998
VLDB
0.0002235043
320
DeepDB: Learn from Data, not from Queries!
2020
VLDB
0.00021128745
405
Deep Unsupervised Cardinality Estimation
2020
VLDB
0.00019020138
452
Mergeable Summaries
2012
PODS
0.00018032092
564
Congressional Samples for Approximate Answering of Group-By Queries
2000
SIGMOD
0.00016251304
667
Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure
2001
SIGMOD
0.00014941252
770
VerdictDB: Universalizing Approximate Query Processing
2018
SIGMOD
0.00014086699
793
Random Sampling over Joins Revisited
2018
SIGMOD
0.00013903938
841
Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters
2016
SIGMOD
0.00013503124
935
Dynamic Sample Selection for Approximate Query Processing
2003
SIGMOD
0.00012968914
1,039
Fine-grained Partitioning for Aggressive Data Skipping
2014
SIGMOD
0.00012349128
1,065
Approximate Query Processing: No Silver Bullet
2017
SIGMOD
0.00012181098
1,186
ICICLES: Self-tuning Samples for Approximate Query Answering
2000
VLDB
0.00011581468
1,693
Global Optimization of Histograms
2001
SIGMOD
9.8377504e-05
1,721
A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data
2014
SIGMOD
9.7821782e-05
2,014
Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee
2016
SIGMOD
9.1775869e-05
2,040
Database Learning: Toward a Database that Becomes Smarter Every Time
2017
SIGMOD
9.1319608e-05
2,661
A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries
2001
SIGMOD
8.1414177e-05
3,428
Revisiting Reuse for Approximate Query Processing
2017
VLDB
7.2957009e-05
3,435
AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics
2018
SIGMOD
7.2845431e-05
3,653
Optimal Histograms for Hierarchical Range Queries (Extended Abstract)
2000
PODS
7.1149642e-05
6,800
Robust Estimation With Sampling and Approximate Pre-Aggregation
2003
VLDB
5.662589e-05
7,175
Learning to Sample: Counting with Complex Queries
2020
VLDB
5.5779755e-05
8,192
Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints
2020
SIGMOD
5.3646457e-05
8,305
Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters
2019
VLDB
5.3427507e-05
8,800
CoopStore: Optimizing Precomputed Summaries for Aggregation
2020
VLDB
5.2602992e-05
8,894
Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views
2015
VLDB
5.2415191e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
7,576
Structure-Aware Sampling: Flexible and Accurate Summarization
2011
VLDB
2
2,661
A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries
2001
SIGMOD
3
935
Dynamic Sample Selection for Approximate Query Processing
2003
SIGMOD
4
1,435
Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems
2014
SIGMOD
5
10,620
Approximate Query Processing under Updates
2026
SIGMOD
6
11,844
Approximate Queries over Concurrent Updates
2023
VLDB
7
3,435
AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics
2018
SIGMOD
8
5,841
Joins on Samples: A Theoretical Guide for Practitioners
2020
VLDB
9
11,149
Efficient Approximate Query Processing with Block Sampling
2025
CIDR
10
2,014
Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee
2016
SIGMOD