Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries
Summary: First asymptotically optimal uniform-sampling and approximate-counting algorithms for matrix, star, and chain join-project queries, using rejection sampling and hybrid reductions. Matching communication lower bounds prove optimality and show sublinear sampling is impossible for general chains. (summarized by gpt-5.6-luna on Jul 26 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Xiao Hu (University of Waterloo)
- 2. Jinchao Huang (Chinese University of Hong Kong)
BibTeX Citation
@inproceedings{hu_pods26,
address = {New York, NY, USA},
series = {{PODS} '26},
title = {{Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries}},
url = {https://dl.acm.org/doi/10.1145/3801916},
doi = {10.1145/3801916},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Hu, Xiao and Huang, Jinchao},
year = {2026}
}Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 10 of 10 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 |
| 136 | Join Synopses for Approximate Query Answering | 1999 | SIGMOD | 0.00030123303 |
| 173 | Simple Random Sampling from Relational Databases | 1986 | VLDB | 0.00027273858 |
| 321 | Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems | 2018 | PODS | 0.00021283186 |
| 411 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00018902089 |
| 802 | Random Sampling over Joins Revisited | 2018 | SIGMOD | 0.00013907725 |
| 3,453 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS | 7.4004131e-05 |
| 3,481 | Tighter Estimation using Bottom k Sketches | 2008 | VLDB | 7.376137e-05 |
| 3,941 | Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins | 2023 | PODS | 7.0074268e-05 |
| 7,143 | Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries | 2020 | PODS | 5.6915726e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 136 | Join Synopses for Approximate Query Answering | 1999 | SIGMOD |
| 2 | 6,412 | Ranked Enumeration of Join Queries with Projections | 2022 | VLDB |
| 3 | 3,813 | Query Simplification: Graceful Degradation for Join-Order Optimization | 2009 | SIGMOD |
| 4 | 3,959 | Simplicity Done Right for Join Ordering | 2021 | CIDR |
| 5 | 5,743 | Joins on Samples: A Theoretical Guide for Practitioners | 2020 | VLDB |
| 6 | 54 | On Random Sampling over Joins | 1999 | SIGMOD |
| 7 | 7,335 | Reservoir Sampling over Joins | 2024 | SIGMOD |
| 8 | 5,364 | Fast Join Project Query Evaluation using Matrix Multiplication | 2020 | SIGMOD |
| 9 | 3,941 | Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins | 2023 | PODS |
| 10 | 3,453 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS |