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
5459
Venue
SIGMOD
Year
2018
Pagerank
0.00012339777
Overall Rank
1,369 | 90.48%
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,254 Secure Multi-Party Sampling over Joins 2026 VLDB 4.1945683e-05
10,324 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB 4.1945683e-05
10,359 Smallest Synthetic Witnesses for Conjunctive Queries 2025 PODS 4.1945683e-05
10,497 PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees 2025 SIGMOD 4.1945683e-05
10,632 Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach 2025 VLDB 4.1945683e-05
10,924 Improved Approximation Algorithms for Relational Clustering 2024 PODS 4.1945683e-05
10,927 Computing A Well-Representative Summary of Conjunctive Query Results 2024 PODS 4.1945683e-05
10,948 gSWORD: GPU-accelerated Sampling for Subgraph Counting 2024 SIGMOD 4.1945683e-05
10,981 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.1945683e-05
11,453 XLJoins 2021 SIGMOD 4.1945683e-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.0010801504
18 On Random Sampling over Joins 1999 SIGMOD 0.00092385438
66 Spark SQL: Relational Data Processing in Spark 2015 SIGMOD 0.00061639801
211 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00033981214
217 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00033536712
549 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020376603
553 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00020272061
834 Learning Linear Regression Models over Factorized Joins 2016 SIGMOD 0.00016135159
943 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015145883
967 Aqua: A Fast Decision Support System Using Approximate Query Answers 1999 VLDB 0.00014959939
1,167 Learning Generalized Linear Models Over Normalized Data 2015 SIGMOD 0.00013547713
1,193 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00013414989
1,323 Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters 2016 SIGMOD 0.00012601997
1,425 Scalable Approximate Query Processing With The DBO Engine 2007 SIGMOD 0.00012051353
1,464 Online Aggregation for Large MapReduce Jobs 2011 VLDB 0.00011865546
1,758 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00010655546
1,939 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00010025655
2,202 A Scalable Hash Ripple Join Algorithm 2002 SIGMOD 9.2987417e-05
2,355 G-OLA: Generalized On-Line Aggregation for Interactive Analysis on Big Data 2015 SIGMOD 8.9677847e-05
2,377 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 8.9402115e-05
2,580 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD 8.5058814e-05
3,594 Continuous Sampling for Online Aggregation Over Multiple Queries 2010 SIGMOD 6.9381343e-05
3,842 Turbo-Charging Estimate Convergence in DBO 2009 VLDB 6.7102374e-05
4,029 Spatial Online Sampling and Aggregation 2016 VLDB 6.51315e-05
4,093 Distributed Online Aggregations 2009 VLDB 6.4558147e-05
5,868 ABS: a System for Scalable Approximate Queries with Accuracy Guarantees 2014 SIGMOD 5.2959352e-05
8,421 The DBO Database System 2008 SIGMOD 4.5170825e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,048 Fast, Randomized Join-Order Selection — Why Use Transformations? 1994 VLDB 7.6543116e-05
4,953 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 5.8085795e-05
10,324 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB 4.1945683e-05
5,951 PGMJoins: Random Join Sampling with Graphical Models 2021 SIGMOD 5.2592385e-05
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051315959
6,493 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB 5.0424713e-05
2,254 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.1897043e-05
46 Simple Random Sampling from Relational Databases 1986 VLDB 0.00070894702
8,959 Reservoir Sampling over Joins 2024 SIGMOD 4.4206222e-05
18 On Random Sampling over Joins 1999 SIGMOD 0.00092385438