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: 10854
Venue: VLDB
Year: 2013
Pagerank: 8.6116764e-05
Overall Rank: 2,413 | 83.45%
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
593	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00016027871
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014147905
819	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00013815639
1,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
2,663	Partial Results in Database Systems	2014	SIGMOD	8.2818137e-05
3,366	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.4748604e-05
3,453	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	7.4004131e-05
3,741	Spatial Online Sampling and Aggregation	2016	VLDB	7.1586403e-05
4,837	PrivateClean: Data Cleaning and Differential Privacy	2016	SIGMOD	6.4845444e-05
7,316	SpareLLM: Automatically Selecting Task-Specific Minimum-Cost Large Language Models under Equivalence Constraint	2025	SIGMOD	5.646695e-05
8,051	Wander Join: Online Aggregation for Joins	2016	SIGMOD	5.4997517e-05
8,204	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.4667903e-05
8,714	Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views	2015	VLDB	5.3778009e-05
8,984	Hit the Gym: Accelerating Query Execution to Efficiently Bootstrap Behavior Models for Self-Driving Database Management Systems	2024	VLDB	5.3395569e-05
10,634	Efficient Approximate Query Processing with Block Sampling	2025	CIDR	5.093636e-05
11,749	BitGourmet: Deterministic Approximation via Optimized Bit Selection	2020	CIDR	5.093636e-05
11,781	Demonstration of BitGourmet: Data Analysis via Deterministic Approximation	2020	SIGMOD	5.093636e-05
12,112	STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data	2015	SIGMOD	5.093636e-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.00077458002
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00048351457
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
131	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00030424509
136	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00030123303
327	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00021091539
931	Aqua: A Fast Decision Support System Using Approximate Query Answers	1999	VLDB	0.00013125812
1,024	The DataPath System: A Data-Centric Analytic Processing Engine for Large Data Warehouses	2010	SIGMOD	0.0001258839
1,064	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012336248
3,157	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	7.6911286e-05
6,562	Query Sampling in DB2 Universal Database	2004	SIGMOD	5.838575e-05

Semantically Similar Papers

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