Approximate Query Processing: Taming the TeraBytes! A Tutorial

Summary: Tutorial on approximate aggregate query processing via online sampling and precomputed synopses with explicit error guarantees. Covers multidimensional data, joins, set-valued queries, Aqua-style architectures, streaming, dependencies, and workload-tuned synopsis design. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9015
Venue: VLDB
Year: 2001
Pagerank: 0.0002005475
Overall Rank: 363 | 97.52%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Minos Garofalakis (AT&T)
2. Phillip B. Gibbons (AT&T)

BibTeX Citation

@article{garofalakis_vldb01,
        title = {{Approximate Query Processing: Taming the TeraBytes! A Tutorial}},
        author = {Garofalakis, Minos and Gibbons, Phillip B.},
        journal = {PVLDB},
        series = {{VLDB} '01},
        pages = {169},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 41 of 41 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
125	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00030932014
337	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020783399
432	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00018572055
569	BlazeIt: Optimizing Declarative Aggregation and Limit Queries for Neural Network-Based Video Analytics	2020	VLDB	0.00016348191
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702
828	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00013769869
1,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
1,147	Data Management Challenges in Production Machine Learning	2017	SIGMOD	0.00011974846
1,227	Blink and It's Done: Interactive Queries on Very Large Data	2012	VLDB	0.00011582387
1,634	Rapid Sampling for Visualizations with Ordering Guarantees	2015	VLDB	0.00010163938
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
2,280	Partial Results for Online Query Processing	2002	SIGMOD	8.8129961e-05
2,367	Using Probabilistic Models for Data Management in Acquisitional Environments	2005	CIDR	8.6855754e-05
2,816	Cache-Craft: Managing Chunk-Caches for Efficient Retrieval-Augmented Generation	2025	SIGMOD	8.0959781e-05
2,987	Incremental and Approximate Inference for Faster Occlusion-based Deep CNN Explanations	2019	SIGMOD	7.8907997e-05
3,072	Lux: Always-on Visualization Recommendations for Exploratory Dataframe Workflows	2022	VLDB	7.7873864e-05
3,288	I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making	2017	VLDB	7.5578177e-05
3,945	Exploiting Correlations for Expensive Predicate Evaluation	2015	SIGMOD	7.0055154e-05
4,264	A Method for Optimizing Opaque Filter Queries	2020	SIGMOD	6.7937529e-05
4,581	Mining Graph Patterns Efficiently via Randomized Summaries	2009	VLDB	6.6198548e-05
4,837	PrivateClean: Data Cleaning and Differential Privacy	2016	SIGMOD	6.4845444e-05
5,868	A Random Walk Approach to Sampling Hidden Databases	2007	SIGMOD	6.0613238e-05
6,038	Efficient Construction of Approximate Ad-Hoc ML models Through Materialization and Reuse	2018	VLDB	5.9990929e-05
6,210	Supporting Our AI Overlords: Redesigning Data Systems to be Agent-First	2026	CIDR	5.9425753e-05
6,712	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	5.7962014e-05
7,389	Benchmarking Spreadsheet Systems	2020	SIGMOD	5.6266966e-05
7,903	Mining a Search Engine’s Corpus: Efficient Yet Unbiased Sampling and Aggregate Estimation	2011	SIGMOD	5.5182155e-05
8,714	Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views	2015	VLDB	5.3778009e-05
9,009	Efficient Approximations of Conjunctive Queries	2012	PODS	5.3335287e-05
9,650	Aggregate Estimation Over Dynamic Hidden Web Databases	2014	VLDB	5.2427667e-05
9,749	Auto-Approximation of Graph Computing	2014	VLDB	5.227679e-05
10,342	Approximate Query Processing under Updates	2026	SIGMOD	5.093636e-05
10,404	Stochastic Submodular Data Forgetting	2026	SIGMOD	5.093636e-05
10,504	Task Cascades for Efficient Unstructured Data Processing	2026	SIGMOD	5.093636e-05
11,109	FaDE: More Than a Million What-ifs Per Second	2025	VLDB	5.093636e-05
11,700	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	5.093636e-05
11,886	Enabling Data Science for the Majority	2019	VLDB	5.093636e-05
12,033	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD	5.093636e-05
12,216	When Data Management Systems Meet Approximate Hardware: Challenges and Opportunities	2014	VLDB	5.093636e-05
12,699	AQAX: A System for Approximate XML Query Answers	2006	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 52 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
4,846	A Comparison of Selectivity Estimators for Range Queries on Metric Attributes	1999	SIGMOD	6.4807645e-05
6,053	Modeling skewed distributions using multifractals and the '80-20 law'	1996	VLDB	5.9939282e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,342	Approximate Query Processing under Updates	2026	SIGMOD
2	10,634	Efficient Approximate Query Processing with Block Sampling	2025	CIDR
3	136	Join Synopses for Approximate Query Answering	1999	SIGMOD
4	307	Approximate Query Processing Using Wavelets	2000	VLDB
5	909	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD
6	4,933	Online Query Processing: A Tutorial	2001	SIGMOD
7	6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD
8	1,401	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD
9	327	The Aqua Approximate Query Answering System	1999	SIGMOD
10	1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD