A Sampling Algebra for Aggregate Estimation

Summary: Generalized uniform sampling (GUS) framework for aggregate estimation. Introduces an equivalence notion that lets GUS operators commute with selections and joins, enabling confidence intervals and practically meaningful estimates in DB systems. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10666
Venue: VLDB
Year: 2013
Pagerank: 7.7587199e-05
Overall Rank: 2,995 | 79.17%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
943	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015145883
1,204	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00013319541
1,323	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00012601997
1,574	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00011287495
3,051	Partial Results in Database Systems	2014	SIGMOD	7.6512591e-05
3,944	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	6.6078243e-05
4,029	Spatial Online Sampling and Aggregation	2016	VLDB	6.51315e-05
4,668	PrivateClean: Data Cleaning and Differential Privacy	2016	SIGMOD	6.0115918e-05
4,953	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8085795e-05
7,339	SpareLLM: Automatically Selecting Task-Specific Minimum-Cost Large Language Models under Equivalence Constraint	2025	SIGMOD	4.7579469e-05
8,689	Wander Join: Online Aggregation for Joins	2016	SIGMOD	4.4667389e-05
8,728	Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views	2015	VLDB	4.4589711e-05
9,006	Hit the Gym: Accelerating Query Execution to Efficiently Bootstrap Behavior Models for Self-Driving Database Management Systems	2024	VLDB	4.4101482e-05
10,337	Efficient Approximate Query Processing with Block Sampling	2025	CIDR	4.1945683e-05
10,497	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	4.1945683e-05
11,552	BitGourmet: Deterministic Approximation via Optimized Bit Selection	2020	CIDR	4.1945683e-05
11,585	Demonstration of BitGourmet: Data Analysis via Deterministic Approximation	2020	SIGMOD	4.1945683e-05
11,913	STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data	2015	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
14	Online Aggregation	1997	SIGMOD	0.0010801504
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080435857
211	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033981214
217	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00033536712
429	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00023476494
967	Aqua: A Fast Decision Support System Using Approximate Query Answers	1999	VLDB	0.00014959939
1,299	The DataPath System: A Data-Centric Analytic Processing Engine for Large Data Warehouses	2010	SIGMOD	0.00012751522
1,425	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012051353
3,842	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	6.7102374e-05
6,548	Query Sampling in DB2 Universal Database	2004	SIGMOD	5.0181595e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
367	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025509745
2,808	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.0870741e-05
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036625711
6,491	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.0429323e-05
762	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017036868
5,415	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	5.5196338e-05
8,350	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	4.5404832e-05
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00070894702
39	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00074745564
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959