Random Sampling over Joins Revisited

Summary: Revisits random sampling over multi-way joins (acyclic and cyclic) with a general framework that subsumes Chaudhuri et al.'s approach. Explores instantiations under different data priors, balancing latency and throughput, and demonstrates superiority over baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h3cff514cb6ec7fb2
Venue: SIGMOD
Year: 2018
Pagerank: 0.00013938779
Overall Rank: 795 | 94.66%
DOI: 10.1145/3183713.3183739

Incoming Non-self Citations Over Time

Authors

1. Zhuoyue Zhao (University of Utah)
2. Robert Christensen (University of Utah)
3. Feifei Li (University of Utah)
4. Xiao Hu (Hong Kong University of Science and Technology)
5. Ke Yi (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{zhao_sigmod18,
        title = {{Random Sampling over Joins Revisited}},
        author = {Zhao, Zhuoyue and Christensen, Robert and Li, Feifei and Hu, Xiao and Yi, Ke},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3183739},
        url = {https://dl.acm.org/doi/10.1145/3183713.3183739},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 66 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,215	Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation	2025	VLDB	5.0584922e-05
10,216	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	5.0584922e-05
10,235	Scalable and Usable Relational Learning With Automatic Language Bias	2021	SIGMOD	5.0547931e-05
10,315	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	5.0377739e-05
10,386	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS	4.9793485e-05
10,402	Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees	2026	SIGMOD	4.9793485e-05
10,422	Bridging the Gap: Cardinality Estimation for Semantic Queries on Unstructured Data	2026	SIGMOD	4.9793485e-05
10,700	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	4.9793485e-05
10,724	Secure Multi-Party Sampling over Joins	2026	VLDB	4.9793485e-05
11,027	Instance-Optimal Acyclic Joins: From Theory to Systems	2026	VLDB	4.9793485e-05
11,068	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	4.9793485e-05
11,095	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.9793485e-05
11,286	Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach	2025	VLDB	4.9793485e-05
11,492	Improved Approximation Algorithms for Relational Clustering	2024	PODS	4.9793485e-05
11,536	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9793485e-05
11,958	XLJoins	2021	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 27 of 27 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
23	Spark SQL: Relational Data Processing in Spark	2015	SIGMOD	0.00055406774
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
428	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.0001845349
521	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016929744
596	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015785583
730	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00014406936
745	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014288286
750	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00014265196
840	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.0001354605
948	Aqua: A Fast Decision Support System Using Approximate Query Answers	1999	VLDB	0.00012914559
1,022	Online Aggregation for Large MapReduce Jobs	2011	VLDB	0.00012438826
1,090	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012077577
1,257	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011310561
1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011152286
1,820	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD	9.5690887e-05
1,868	G-OLA: Generalized On-Line Aggregation for Interactive Analysis on Big Data	2015	SIGMOD	9.4754064e-05
1,891	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.4184294e-05
2,000	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.2112617e-05
3,087	Continuous Sampling for Online Aggregation Over Multiple Queries	2010	SIGMOD	7.6624333e-05
3,213	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	7.5328015e-05
3,818	Spatial Online Sampling and Aggregation	2016	VLDB	7.0060535e-05
3,905	Distributed Online Aggregations	2009	VLDB	6.9335334e-05
5,473	ABS: a System for Scalable Approximate Queries with Accuracy Guarantees	2014	SIGMOD	6.1178467e-05
8,543	The DBO Database System	2008	SIGMOD	5.3187151e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,386	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS
2	5,657	PGMJoins: Random Join Sampling with Graphical Models	2021	SIGMOD
3	79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
4	5,831	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB
5	8,279	Subset Sampling over Joins	2026	PODS
6	1,678	Two-Level Sampling for Join Size Estimation	2017	SIGMOD
7	9,634	Poisson Sampling over Acyclic Joins	2026	SIGMOD
8	175	Simple Random Sampling from Relational Databases	1986	VLDB
9	7,467	Reservoir Sampling over Joins	2024	SIGMOD
10	57	On Random Sampling over Joins	1999	SIGMOD