DBScholar

Back to papers

Poisson Sampling over Acyclic Joins

Summary: Introduces near-instance-optimal Poisson sampling for acyclic joins with tuple-specific probabilities, avoiding full materialization via random-access join indexes. Achieves O(|db| + k log |db|) time and a shared basis for sampling and Yannakakis-style processing. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID
h1f7ad15909e489ae
Venue
SIGMOD
Year
2026
Pagerank
5.146966e-05
Overall Rank
9,634 | 35.23%
DOI
10.1145/3802101

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{bekkers_sigmod26,
        title = {{Poisson Sampling over Acyclic Joins}},
        author = {Bekkers, Liese and Neven, Frank and Pantelis, Lorrens and Vansummeren, Stijn},
        series = {{SIGMOD} '26},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3802101},
        url = {https://dl.acm.org/doi/10.1145/3802101},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank Citing Paper Year Venue Pagerank
8,279 Subset Sampling over Joins 2026 PODS 5.3637624e-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 18 of 18 cited papers.

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

Rank Cited Paper Year Venue Pagerank
15 How Good Are Query Optimizers, Really? 2016 VLDB 0.00061066921
57 On Random Sampling over Joins 1999 SIGMOD 0.00040108301
135 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00029866033
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029627449
795 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013938779
982 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00012714044
1,009 Simulation of Database-Valued Markov Chains Using SimSQL 2013 SIGMOD 0.00012539827
2,169 Normal Forms and Conservative Properties for Query Languages over Collection Types 1993 PODS 8.9247938e-05
2,757 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.0525756e-05
3,212 Query Shredding: Efficient Relational Evaluation of Queries over Nested Multisets 2014 SIGMOD 7.5328945e-05
4,369 Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries 2024 CIDR 6.6315141e-05
4,950 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.3421691e-05
5,902 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9536872e-05
6,805 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6780394e-05
7,246 Efficient Dynamic Weighted Set Sampling and Its Extension 2024 VLDB 5.5750011e-05
7,467 Reservoir Sampling over Joins 2024 SIGMOD 5.5198675e-05
7,917 Avoiding Materialisation for Guarded Aggregate Queries 2025 VLDB 5.4276002e-05
8,279 Subset Sampling over Joins 2026 PODS 5.3637624e-05
Previous Page 1 / 1 Next

Semantically Similar Papers