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: h4014809093bd5f22
Venue: SIGMOD
Year: 2001
Pagerank: 8.1706092e-05
Overall Rank: 2,655 | 82.16%
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.00052121228
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022722971
372	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019720059
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,082	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012122749
1,242	Compressing SQL Workloads	2002	SIGMOD	0.00011373611
2,000	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.2112617e-05
2,322	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.6361485e-05
2,396	Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? *	2005	CIDR	8.5278724e-05
3,424	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.3117029e-05
4,252	Primitives for Workload Summarization and Implications for SQL	2003	VLDB	6.7015609e-05
5,930	Hillview: A trillion-cell spreadsheet for big data	2019	VLDB	5.9438354e-05
6,221	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.8463347e-05
6,781	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.6836871e-05
7,907	A Practical Approach to Groupjoin and Nested Aggregates	2021	VLDB	5.4287568e-05
8,283	Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters	2019	VLDB	5.3627138e-05
8,363	Probabilistic Database Summarization for Interactive Data Exploration	2017	VLDB	5.3472423e-05
9,103	STAR: Self-Tuning Aggregation for Scalable Monitoring	2007	VLDB	5.2283159e-05
12,039	FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data	2021	VLDB	4.9793485e-05
12,328	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD	4.9793485e-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.00076195956
57	On Random Sampling over Joins	1999	SIGMOD	0.00040108301
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029627449
222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024218831
309	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021384073
448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00018129161
564	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016296665
1,183	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00011616705

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	931	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD
2	1,428	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD
3	8,283	Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters	2019	VLDB
4	4,792	Error-bounded Sampling for Analytics on Big Sparse Data	2014	VLDB
5	6,221	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	569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
8	6,781	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB
9	2,000	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD
10	448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB