A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries

Summary: Optimization-based framework for approximate aggregate queries, minimizing error across workloads. Robust sampling tailored to workload variants with principled variance handling; DBMS-implementable; experiments on SQL Server 2000 show improved accuracy over prior work. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3339
Venue: SIGMOD
Year: 2001
Pagerank: 8.347674e-05
Overall Rank: 2,608 | 82.11%
DOI: 10.1145/375663.375694

Incoming Non-self Citations Over Time

Authors

1. Surajit Chaudhuri (Microsoft)
2. Gautam Das (Microsoft)
3. Vivek Narasayya (Microsoft)

BibTeX Citation

@inproceedings{chaudhuri_sigmod01,
        title = {{A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries}},
        author = {Chaudhuri, Surajit and Das, Gautam and Narasayya, Vivek},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375694},
        url = {https://dl.acm.org/doi/10.1145/375663.375694},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
363	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.0002005475
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,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
1,266	Compressing SQL Workloads	2002	SIGMOD	0.00011412078
1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.3978414e-05
2,271	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.8254873e-05
2,359	Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? *	2005	CIDR	8.698016e-05
3,366	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.4748604e-05
4,198	Primitives for Workload Summarization and Implications for SQL	2003	VLDB	6.8397659e-05
6,028	Hillview: A trillion-cell spreadsheet for big data	2019	VLDB	6.0019322e-05
6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.9443409e-05
6,654	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.8131331e-05
7,787	A Practical Approach to Groupjoin and Nested Aggregates	2021	VLDB	5.5449593e-05
8,108	Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters	2019	VLDB	5.4850569e-05
8,191	Probabilistic Database Summarization for Interactive Data Exploration	2017	VLDB	5.4699738e-05
8,940	STAR: Self-Tuning Aggregation for Scalable Monitoring	2007	VLDB	5.3483178e-05
11,736	FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data	2021	VLDB	5.093636e-05
12,033	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
136	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00030123303
213	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024723025
307	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021792475
435	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.000185063
553	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016590619
1,166	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00011850439

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	909	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD
2	1,401	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD
3	8,108	Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters	2019	VLDB
4	4,696	Error-bounded Sampling for Analytics on Big Sparse Data	2014	VLDB
5	6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD
6	682	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB
7	566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
8	6,654	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB
9	1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD
10	435	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB