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: 10667
Venue: VLDB
Year: 2013
Pagerank: 7.7606324e-05
Overall Rank: 2,995 | 79.19%
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
941	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015147831
1,161	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00013579831
1,320	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00012606067
1,574	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00011289028
3,054	Partial Results in Database Systems	2014	SIGMOD	7.6478475e-05
3,944	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	6.6056349e-05
4,032	Spatial Online Sampling and Aggregation	2016	VLDB	6.5131946e-05
4,664	PrivateClean: Data Cleaning and Differential Privacy	2016	SIGMOD	6.0058132e-05
4,926	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8184457e-05
7,335	SpareLLM: Automatically Selecting Task-Specific Minimum-Cost Large Language Models under Equivalence Constraint	2025	SIGMOD	4.7533835e-05
8,685	Wander Join: Online Aggregation for Joins	2016	SIGMOD	4.4624568e-05
8,703	Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views	2015	VLDB	4.4596255e-05
9,012	Hit the Gym: Accelerating Query Execution to Efficiently Bootstrap Behavior Models for Self-Driving Database Management Systems	2024	VLDB	4.4059413e-05
9,238	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	4.3648789e-05
10,349	Efficient Approximate Query Processing with Block Sampling	2025	CIDR	4.1905499e-05
11,556	BitGourmet: Deterministic Approximation via Optimized Bit Selection	2020	CIDR	4.1905499e-05
11,589	Demonstration of BitGourmet: Data Analysis via Deterministic Approximation	2020	SIGMOD	4.1905499e-05
11,921	STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data	2015	SIGMOD	4.1905499e-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.0010813443
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080571183
212	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033997204
216	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00033560137
431	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00023397171
960	Aqua: A Fast Decision Support System Using Approximate Query Answers	1999	VLDB	0.00015031055
1,296	The DataPath System: A Data-Centric Analytic Processing Engine for Large Data Warehouses	2010	SIGMOD	0.00012742585
1,425	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012044433
3,808	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	6.7416988e-05
6,543	Query Sampling in DB2 Universal Database	2004	SIGMOD	5.0139217e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
369	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025502381
2,813	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.0816314e-05
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
6,485	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.0386161e-05
5,423	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	5.5143276e-05
751	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017155121
8,345	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	4.5361313e-05
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00071588702
37	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00075597514
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888