ICICLES: Self-tuning Samples for Approximate Query Answering

Summary: Introduces workload-adaptive “icicle” samples for approximate aggregate queries over foreign-key joins, allocating tuple inclusion probability by query importance rather than uniformly. Self-tuning samples exploit OLAP locality to improve accuracy under fixed storage, with analytical guarantees and experiments. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h70bbbf3ace0c26ad
Venue: VLDB
Year: 2000
Pagerank: 0.00011616705
Overall Rank: 1,183 | 92.05%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Venkatesh Ganti (University of Wisconsin)
2. Mong Li Lee (University of Wisconsin)
3. Raghu Ramakrishnan (University of Wisconsin)

BibTeX Citation

@article{ganti_vldb00,
        title = {{ICICLES: Self-tuning Samples for Approximate Query Answering}},
        author = {Ganti, Venkatesh and Lee, Mong Li and Ramakrishnan, Raghu},
        journal = {PVLDB},
        series = {{VLDB} '00},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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
784	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014012614
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
1,607	SciBORQ: Scientific data management with Bounds On Runtime and Quality	2011	CIDR	0.0001008742
2,000	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.2112617e-05
2,027	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	9.1618139e-05
2,322	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.6361485e-05
2,655	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.1706092e-05
3,361	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD	7.3760492e-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
4,792	Error-bounded Sampling for Analytics on Big Sparse Data	2014	VLDB	6.4130671e-05
5,021	Adaptive Sampling for Rapidly Matching Histograms	2018	VLDB	6.3106761e-05
5,831	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.9782109e-05
5,927	A Database System with Amnesia	2017	CIDR	5.9441754e-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
8,223	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.3751366e-05
8,856	Adaptive Index Structures	2002	VLDB	5.2635701e-05
12,039	FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data	2021	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028633995
222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024218831
336	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00020657819
1,764	Caching Multidimensional Queries Using Chunks	1998	SIGMOD	9.6965217e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD
2	931	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD
3	840	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD
4	11,079	Efficient Approximate Query Processing with Block Sampling	2025	CIDR
5	138	Join Synopses for Approximate Query Answering	1999	SIGMOD
6	6,221	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD
7	8,283	Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters	2019	VLDB
8	2,655	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD
9	2,000	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD
10	1,428	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD