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.4377192e-05
Overall Rank: 2,456 | 83.49%
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
596	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015785583
784	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014012614
840	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.0001354605
1,082	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012122749
2,717	Partial Results in Database Systems	2014	SIGMOD	8.0980367e-05
3,424	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.3117029e-05
3,494	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	7.2582926e-05
3,818	Spatial Online Sampling and Aggregation	2016	VLDB	7.0060535e-05
4,960	PrivateClean: Data Cleaning and Differential Privacy	2016	SIGMOD	6.3390487e-05
6,860	SpareLLM: Automatically Selecting Task-Specific Minimum-Cost Large Language Models under Equivalence Constraint	2025	SIGMOD	5.6613762e-05
8,216	Wander Join: Online Aggregation for Joins	2016	SIGMOD	5.3764262e-05
8,223	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.3751366e-05
8,870	Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views	2015	VLDB	5.2601766e-05
9,133	Hit the Gym: Accelerating Query Execution to Efficiently Bootstrap Behavior Models for Self-Driving Database Management Systems	2024	VLDB	5.2229655e-05
11,079	Efficient Approximate Query Processing with Block Sampling	2025	CIDR	4.9793485e-05
12,052	BitGourmet: Deterministic Approximation via Optimized Bit Selection	2020	CIDR	4.9793485e-05
12,083	Demonstration of BitGourmet: Data Analysis via Deterministic Approximation	2020	SIGMOD	4.9793485e-05
12,405	STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data	2015	SIGMOD	4.9793485e-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.00076195956
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047863192
57	On Random Sampling over Joins	1999	SIGMOD	0.00040108301
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029866033
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029627449
336	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00020657819
948	Aqua: A Fast Decision Support System Using Approximate Query Answers	1999	VLDB	0.00012914559
1,040	The DataPath System: A Data-Centric Analytic Processing Engine for Large Data Warehouses	2010	SIGMOD	0.00012364063
1,090	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012077577
3,213	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	7.5328015e-05
6,685	Query Sampling in DB2 Universal Database	2004	SIGMOD	5.7086005e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	346	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD
2	2,655	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,781	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB
5	1,011	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS
6	6,118	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB
7	8,347	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