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.00013903938
Overall Rank: 793 | 94.69%
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,221	Path-centric Cardinality Estimation for Subgraph Matching	2025	VLDB	5.0460607e-05
10,257	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	5.039379e-05
10,273	Scalable and Usable Relational Learning With Automatic Language Bias	2021	SIGMOD	5.0356939e-05
10,345	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	5.0197268e-05
10,464	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS	4.9605343e-05
10,480	Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees	2026	SIGMOD	4.9605343e-05
10,500	Bridging the Gap: Cardinality Estimation for Semantic Queries on Unstructured Data	2026	SIGMOD	4.9605343e-05
10,771	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	4.9605343e-05
10,795	Secure Multi-Party Sampling over Joins	2026	VLDB	4.9605343e-05
11,097	Instance-Optimal Acyclic Joins: From Theory to Systems	2026	VLDB	4.9605343e-05
11,138	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	4.9605343e-05
11,165	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.9605343e-05
11,349	Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach	2025	VLDB	4.9605343e-05
11,550	Improved Approximation Algorithms for Relational Clustering	2024	PODS	4.9605343e-05
11,591	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9605343e-05
12,008	XLJoins	2021	SIGMOD	4.9605343e-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.00076079812
23	Spark SQL: Relational Data Processing in Spark	2015	SIGMOD	0.00055523999
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
432	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018400309
522	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016893112
594	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015814493
731	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00014363943
750	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014246313
752	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00014234789
841	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00013503124
951	Aqua: A Fast Decision Support System Using Approximate Query Answers	1999	VLDB	0.00012886042
1,022	Online Aggregation for Large MapReduce Jobs	2011	VLDB	0.00012400958
1,095	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012036913
1,261	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011289724
1,296	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011119184
1,832	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD	9.5365548e-05
1,874	G-OLA: Generalized On-Line Aggregation for Interactive Analysis on Big Data	2015	SIGMOD	9.4470874e-05
1,896	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.4010932e-05
2,014	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.1775869e-05
3,092	Continuous Sampling for Online Aggregation Over Multiple Queries	2010	SIGMOD	7.638249e-05
3,220	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	7.5077984e-05
3,825	Spatial Online Sampling and Aggregation	2016	VLDB	6.9795872e-05
3,912	Distributed Online Aggregations	2009	VLDB	6.9103187e-05
5,487	ABS: a System for Scalable Approximate Queries with Accuracy Guarantees	2014	SIGMOD	6.0974772e-05
8,570	The DBO Database System	2008	SIGMOD	5.298954e-05

Semantically Similar Papers

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