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: 5521
Venue: SIGMOD
Year: 2018
Pagerank: 0.00013907725
Overall Rank: 802 | 94.50%
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 15 of 65 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,028	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	5.1745962e-05
10,042	Scalable and Usable Relational Learning With Automatic Language Bias	2021	SIGMOD	5.1708123e-05
10,093	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	5.1530576e-05
10,169	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS	5.093636e-05
10,186	Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees	2026	SIGMOD	5.093636e-05
10,206	Bridging the Gap: Cardinality Estimation for Semantic Queries on Unstructured Data	2026	SIGMOD	5.093636e-05
10,515	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	5.093636e-05
10,542	Secure Multi-Party Sampling over Joins	2026	VLDB	5.093636e-05
10,622	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	5.093636e-05
10,652	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	5.093636e-05
10,885	Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach	2025	VLDB	5.093636e-05
11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS	5.093636e-05
11,165	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD	5.093636e-05
11,194	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	5.093636e-05
11,651	XLJoins	2021	SIGMOD	5.093636e-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.00077458002
24	Spark SQL: Relational Data Processing in Spark	2015	SIGMOD	0.00054865648
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
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
536	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.0001693369
593	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00016027871
715	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00014655327
730	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014539362
737	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00014490983
819	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00013815639
931	Aqua: A Fast Decision Support System Using Approximate Query Answers	1999	VLDB	0.00013125812
1,009	Online Aggregation for Large MapReduce Jobs	2011	VLDB	0.00012684342
1,064	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012336248
1,256	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011457194
1,320	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011166426
1,785	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD	9.7702627e-05
1,827	G-OLA: Generalized On-Line Aggregation for Interactive Analysis on Big Data	2015	SIGMOD	9.6690206e-05
1,893	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.5269935e-05
1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.3978414e-05
3,042	Continuous Sampling for Online Aggregation Over Multiple Queries	2010	SIGMOD	7.8231049e-05
3,157	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	7.6911286e-05
3,741	Spatial Online Sampling and Aggregation	2016	VLDB	7.1586403e-05
3,844	Distributed Online Aggregations	2009	VLDB	7.0782059e-05
5,358	ABS: a System for Scalable Approximate Queries with Accuracy Guarantees	2014	SIGMOD	6.2492955e-05
8,398	The DBO Database System	2008	SIGMOD	5.4342404e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,169	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS
2	5,551	PGMJoins: Random Join Sampling with Graphical Models	2021	SIGMOD
3	76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
4	5,743	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB
5	9,719	Subset Sampling over Joins	2026	PODS
6	1,664	Two-Level Sampling for Join Size Estimation	2017	SIGMOD
7	9,512	Poisson Sampling over Acyclic Joins	2026	SIGMOD
8	173	Simple Random Sampling from Relational Databases	1986	VLDB
9	7,335	Reservoir Sampling over Joins	2024	SIGMOD
10	54	On Random Sampling over Joins	1999	SIGMOD