Database Paper Browser

Back to papers

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
5460
Venue
SIGMOD
Year
2018
Pagerank
0.0001233325
Overall Rank
1,372 | 90.47%
DOI
10.1145/3183713.3183739

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 10 of 60 citing papers.

Rank Citing Paper Year Venue Pagerank
10,096 NeuSO: Neural Optimizer for Subgraph Queries 2026 SIGMOD 4.1905499e-05
10,227 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB 4.1905499e-05
10,254 Secure Multi-Party Sampling over Joins 2026 VLDB 4.1905499e-05
10,336 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB 4.1905499e-05
10,371 Smallest Synthetic Witnesses for Conjunctive Queries 2025 PODS 4.1905499e-05
10,640 Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach 2025 VLDB 4.1905499e-05
10,928 Improved Approximation Algorithms for Relational Clustering 2024 PODS 4.1905499e-05
10,951 gSWORD: GPU-accelerated Sampling for Subgraph Counting 2024 SIGMOD 4.1905499e-05
10,984 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.1905499e-05
11,456 XLJoins 2021 SIGMOD 4.1905499e-05
Previous Page 2 / 2 Next

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
14 Online Aggregation 1997 SIGMOD 0.0010813443
18 On Random Sampling over Joins 1999 SIGMOD 0.00092569117
66 Spark SQL: Relational Data Processing in Spark 2015 SIGMOD 0.00061707583
212 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00033997204
216 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00033560137
550 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020346247
553 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00020272747
832 Learning Linear Regression Models over Factorized Joins 2016 SIGMOD 0.00016089705
941 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015147831
960 Aqua: A Fast Decision Support System Using Approximate Query Answers 1999 VLDB 0.00015031055
1,172 Learning Generalized Linear Models Over Normalized Data 2015 SIGMOD 0.00013504249
1,194 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00013411666
1,320 Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters 2016 SIGMOD 0.00012606067
1,425 Scalable Approximate Query Processing With The DBO Engine 2007 SIGMOD 0.00012044433
1,451 Online Aggregation for Large MapReduce Jobs 2011 VLDB 0.00011925842
1,756 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00010659753
1,938 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00010025547
2,208 A Scalable Hash Ripple Join Algorithm 2002 SIGMOD 9.2887018e-05
2,354 G-OLA: Generalized On-Line Aggregation for Interactive Analysis on Big Data 2015 SIGMOD 8.9748896e-05
2,369 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 8.9462051e-05
2,583 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD 8.4973431e-05
3,596 Continuous Sampling for Online Aggregation Over Multiple Queries 2010 SIGMOD 6.9342283e-05
3,808 Turbo-Charging Estimate Convergence in DBO 2009 VLDB 6.7416988e-05
4,032 Spatial Online Sampling and Aggregation 2016 VLDB 6.5131946e-05
4,083 Distributed Online Aggregations 2009 VLDB 6.4583812e-05
5,867 ABS: a System for Scalable Approximate Queries with Accuracy Guarantees 2014 SIGMOD 5.2933639e-05
8,416 The DBO Database System 2008 SIGMOD 4.512905e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,053 Fast, Randomized Join-Order Selection — Why Use Transformations? 1994 VLDB 7.6482987e-05
4,926 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 5.8184457e-05
10,336 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB 4.1905499e-05
5,952 PGMJoins: Random Join Sampling with Graphical Models 2021 SIGMOD 5.2547498e-05
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051431888
6,481 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB 5.039683e-05
2,254 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.1871115e-05
46 Simple Random Sampling from Relational Databases 1986 VLDB 0.00071588702
8,964 Reservoir Sampling over Joins 2024 SIGMOD 4.4163852e-05
18 On Random Sampling over Joins 1999 SIGMOD 0.00092569117