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
h1619d5d26f266616
Venue
PODS
Year
2026
Pagerank
5.3637624e-05
Overall Rank
8,279 | 44.34%
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 2 of 2 citing papers.

Rank Citing Paper Year Venue Pagerank
9,634 Poisson Sampling over Acyclic Joins 2026 SIGMOD 5.146966e-05
11,027 Instance-Optimal Acyclic Joins: From Theory to Systems 2026 VLDB 4.9793485e-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
57 On Random Sampling over Joins 1999 SIGMOD 0.00040108301
135 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00029866033
315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021246
521 Learning Linear Regression Models over Factorized Joins 2016 SIGMOD 0.00016929744
596 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015785583
637 Answering Conjunctive Queries under Updates 2017 PODS 0.00015341557
730 Learning Generalized Linear Models Over Normalized Data 2015 SIGMOD 0.00014406936
795 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013938779
2,757 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.0525756e-05
3,494 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.2582926e-05
3,992 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 6.8685334e-05
4,698 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.4640177e-05
5,989 Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue 2024 PODS 5.9253439e-05
7,467 Reservoir Sampling over Joins 2024 SIGMOD 5.5198675e-05
7,513 Computing A Well-Representative Summary of Conjunctive Query Results 2024 PODS 5.5049463e-05
9,634 Poisson Sampling over Acyclic Joins 2026 SIGMOD 5.146966e-05
9,635 Optimal Dynamic Parameterized Subset Sampling 2024 PODS 5.146966e-05
10,393 Clustering with Set Outliers and Applications in Relational Clustering 2026 PODS 4.9793485e-05
11,492 Improved Approximation Algorithms for Relational Clustering 2024 PODS 4.9793485e-05
Previous Page 1 / 1 Next

Semantically Similar Papers