DBScholar

Back to papers

Subset Sampling over Joins

Summary: Introduces the first efficient subset (Poisson) sampling algorithms over implicitly defined acyclic joins, with probabilities from decomposable tuple-weight functions. Provides static, one-shot, and insertion-dynamic indexes achieving near-optimal input-size and expected-sample-size bounds without materializing the join. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID
2043
Venue
PODS
Year
2026
Pagerank
5.2319816e-05
Overall Rank
9,719 | 33.32%
DOI
10.1145/3801913

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{esmailpour_pods26,
        address = {New York, NY, USA},
        series = {{PODS} '26},
        title = {{Subset Sampling over Joins}},
        url = {https://dl.acm.org/doi/10.1145/3801913},
        doi = {10.1145/3801913},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Esmailpour, Aryan and Hu, Xiao and Huang, Jinchao and Sintos, Stavros},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank Citing Paper Year Venue Pagerank
9,512 Poisson Sampling over Acyclic Joins 2026 SIGMOD 5.2571354e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
54 On Random Sampling over Joins 1999 SIGMOD 0.00040810225
131 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00030424509
321 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021283186
536 Learning Linear Regression Models over Factorized Joins 2016 SIGMOD 0.0001693369
593 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00016027871
636 Answering Conjunctive Queries under Updates 2017 PODS 0.0001551856
715 Learning Generalized Linear Models Over Normalized Data 2015 SIGMOD 0.00014655327
802 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013907725
2,777 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.1352657e-05
3,453 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.4004131e-05
3,941 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 7.0074268e-05
4,781 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.5116536e-05
5,918 Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue 2024 PODS 6.0427671e-05
7,335 Reservoir Sampling over Joins 2024 SIGMOD 5.64193e-05
8,728 Computing A Well-Representative Summary of Conjunctive Query Results 2024 PODS 5.3766157e-05
9,512 Poisson Sampling over Acyclic Joins 2026 SIGMOD 5.2571354e-05
9,513 Optimal Dynamic Parameterized Subset Sampling 2024 PODS 5.2571354e-05
10,176 Clustering with Set Outliers and Applications in Relational Clustering 2026 PODS 5.093636e-05
11,144 Improved Approximation Algorithms for Relational Clustering 2024 PODS 5.093636e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,048 Learning to Sample: Counting with Complex Queries 2020 VLDB
2 10,186 Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees 2026 SIGMOD
3 10,169 Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries 2026 PODS
4 1,664 Two-Level Sampling for Join Size Estimation 2017 SIGMOD
5 173 Simple Random Sampling from Relational Databases 1986 VLDB
6 54 On Random Sampling over Joins 1999 SIGMOD
7 802 Random Sampling over Joins Revisited 2018 SIGMOD
8 3,453 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS
9 9,512 Poisson Sampling over Acyclic Joins 2026 SIGMOD
10 7,335 Reservoir Sampling over Joins 2024 SIGMOD