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: h07e391fd91fffcf0
Venue: VLDB
Year: 2013
Pagerank: 8.4123214e-05
Overall Rank: 2,461 | 83.51%
DOI: 10.14778/2556549.2556563

Incoming Non-self Citations Over Time

Authors

1. Supriya Nirkhiwale (University of Florida)
2. Alin Dobra (University of Florida)
3. Christopher Jermaine (Rice University)

BibTeX Citation

@article{nirkhiwale_vldb13,
        title = {{A Sampling Algebra for Aggregate Estimation}},
        author = {Nirkhiwale, Supriya and Dobra, Alin and Jermaine, Christopher},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {14},
        pages = {1798--1809},
        doi = {10.14778/2556549.2556563},
        url = {https://doi.org/10.14778/2556549.2556563},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
594	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015814493
770	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014086699
841	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00013503124
1,065	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012181098
2,730	Partial Results in Database Systems	2014	SIGMOD	8.0676725e-05
3,435	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.2845431e-05
3,502	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	7.2308675e-05
3,825	Spatial Online Sampling and Aggregation	2016	VLDB	6.9795872e-05
4,984	PrivateClean: Data Cleaning and Differential Privacy	2016	SIGMOD	6.3150969e-05
6,874	SpareLLM: Automatically Selecting Task-Specific Minimum-Cost Large Language Models under Equivalence Constraint	2025	SIGMOD	5.6434298e-05
7,745	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.4457135e-05
8,240	Wander Join: Online Aggregation for Joins	2016	SIGMOD	5.3561117e-05
8,894	Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views	2015	VLDB	5.2415191e-05
9,154	Hit the Gym: Accelerating Query Execution to Efficiently Bootstrap Behavior Models for Self-Driving Database Management Systems	2024	VLDB	5.2050937e-05
11,149	Efficient Approximate Query Processing with Block Sampling	2025	CIDR	4.9605343e-05
12,102	BitGourmet: Deterministic Approximation via Optimized Bit Selection	2020	CIDR	4.9605343e-05
12,133	Demonstration of BitGourmet: Data Analysis via Deterministic Approximation	2020	SIGMOD	4.9605343e-05
12,454	STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data	2015	SIGMOD	4.9605343e-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
9	Online Aggregation	1997	SIGMOD	0.00076079812
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047770864
57	On Random Sampling over Joins	1999	SIGMOD	0.0003999751
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029805026
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029532435
337	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00020593498
951	Aqua: A Fast Decision Support System Using Approximate Query Answers	1999	VLDB	0.00012886042
1,043	The DataPath System: A Data-Centric Analytic Processing Engine for Large Data Warehouses	2010	SIGMOD	0.00012325755
1,095	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012036913
3,220	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	7.5077984e-05
6,703	Query Sampling in DB2 Universal Database	2004	SIGMOD	5.687355e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	346	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD
2	2,661	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD
3	153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD
4	6,800	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB
5	6,133	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB
6	1,012	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS
7	8,363	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR
8	175	Simple Random Sampling from Relational Databases	1986	VLDB
9	58	Statistical Estimators for Relational Algebra Expressions	1988	PODS
10	79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD