{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T01:20:24Z","timestamp":1789435224255,"version":"build-2803163510"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"Bijzonder Onderzoeksfonds","award":["BOF22DOC07"],"award-info":[{"award-number":["BOF22DOC07"]}]},{"name":"Bijzonder Onderzoeksfonds","award":["BOF20ZAP02"],"award-info":[{"award-number":["BOF20ZAP02"]}]},{"DOI":"10.13039\/501100003130","name":"Research Foundation Flanders","doi-asserted-by":"crossref","award":["G0B9623N"],"award-info":[{"award-number":["G0B9623N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>\n                    We introduce the problem of Poisson sampling over joins: compute a sample of the result of a join query by conceptually performing a Bernoulli trial for each join tuple, using a non-uniform and tuple-specific probability. We propose an algorithm for Poisson sampling over acyclic joins that is nearly instance-optimal, running in time \ud835\udc44 (|db| + k \u0142og |db|) where |db| is the size of the input database, and\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    is the size of the resulting sample. Our algorithm hinges on two building blocks: (1) The construction of a random-access index that allows, given a number\n                    <jats:italic toggle=\"yes\">i<\/jats:italic>\n                    , to randomly access the\n                    <jats:italic toggle=\"yes\">i<\/jats:italic>\n                    -th join tuple without fully materializing the (possibly large) join result; (2) The probing of this index to construct the result sample. We study the engineering trade-offs required to make both components practical, focusing on their implementation in column stores, and identify best-performing alternatives for both. Our experiments show that this pair of alternatives significantly outperforms the repeated-Bernoulli-trial algorithm for Poisson sampling while also demonstrating that the random-access index by itself can be used to competively implement Yannakakis' acyclic join processing algorithm when no sampling is required. This shows that, as far a query engine design is concerned, it is possible to adopt a common basis for both classical acyclic join processing and Poisson sampling, both without regret compared to classical join and sampling algorithms.\n                  <\/jats:p>","DOI":"10.1145\/3802101","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-26","source":"Crossref","is-referenced-by-count":1,"title":["Poisson Sampling over Acyclic Joins"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2725-2131","authenticated-orcid":false,"given":"Liese","family":"Bekkers","sequence":"first","affiliation":[{"name":"UHasselt, Data Science Institute, Hasselt, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7143-1903","authenticated-orcid":false,"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"UHasselt, Data Science Institute, Hasselt, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4882-2326","authenticated-orcid":false,"given":"Lorrens","family":"Pantelis","sequence":"additional","affiliation":[{"name":"UHasselt, Data Science Institute, Hasselt, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7793-9049","authenticated-orcid":false,"given":"Stijn","family":"Vansummeren","sequence":"additional","affiliation":[{"name":"UHasselt, Data Science Institute, Hasselt, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304207"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802489"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3742728.3742737"},{"key":"e_1_2_1_4_1","unstructured":"Liese Bekkers Lorrens Pantelis Frank Neven and Stijn Vansummeren. 2026. Poisson Sampling over Acyclic Joins. Technical Report. Full paper version available at https:\/\/arxiv.org\/abs\/2603.10982."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CSL.2012.137"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465283"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3531055"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304206"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612186"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3733620.3733635"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00301-1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8643-8"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3801913"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_2_1_15_1","unstructured":"M. H. Graham. 1979. On the universal relation. Technical Report. University of Toronto Toronto Ontario Canada."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304208"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503586"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1097\/EDE.0000000000001047"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12879-021-05949-4"},{"key":"e_1_2_1_20_1","volume-title":"Yisu Remy Wang, and Daniel P Miranker","author":"Hu Zeyuan","year":"2024","unstructured":"Zeyuan Hu, Yisu Remy Wang, and Daniel P Miranker. 2024. TreeTracker Join: Simple, Optimal, Fast. arXiv preprint arXiv:2403.01631 (2024)."},{"key":"e_1_2_1_21_1","unstructured":"Jinchao Huang and Sibo Wang. 2023. Subset Sampling and Its Extensions. arXiv:2307.11585 [cs.DS] https:\/\/arxiv.org\/abs\/2307.11585"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000824.2000828"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/42372.42381"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3718057.3718068"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284551"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355749"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725423"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0048695"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12879-017-2699-8"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/153850.153853"},{"key":"e_1_2_1_33_1","volume-title":"Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries. In 14th Conference on Innovative Data Systems Research, CIDR 2024","author":"Yang Yifei","year":"2024","unstructured":"Yifei Yang, Hangdong Zhao, Xiangyao Yu, and Paraschos Koutris. 2024. Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries. In 14th Conference on Innovative Data Systems Research, CIDR 2024, Chaminade, HI, USA, January 14-17, 2024. www.cidrdb.org. https:\/\/www.cidrdb.org\/cidr2024\/papers\/p22-yang.pdf"},{"key":"e_1_2_1_34_1","first-page":"9 82","volume-title":"7th International Conference, September","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In Very Large Data Bases, 7th International Conference, September, 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society, 82-94."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/CMPSAC.1979.762509"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3617838.3617840"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725283"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183739"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:20:41Z","timestamp":1779128441000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802101"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802101"],"URL":"https:\/\/doi.org\/10.1145\/3802101","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}