{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T09:47:01Z","timestamp":1774950421251,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":59,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,18]],"date-time":"2023-06-18T00:00:00Z","timestamp":1687046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"HKRGC","award":["14207820, 14203421, 14222822"],"award-info":[{"award-number":["14207820, 14203421, 14222822"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,18]]},"DOI":"10.1145\/3584372.3588666","type":"proceedings-article","created":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T22:21:22Z","timestamp":1685744482000},"page":"99-111","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-7883-3458","authenticated-orcid":false,"given":"Shiyuan","family":"Deng","sequence":"first","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7517-7252","authenticated-orcid":false,"given":"Shangqi","family":"Lu","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3883-5452","authenticated-orcid":false,"given":"Yufei","family":"Tao","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong, Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2023,6,18]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.16"},{"key":"e_1_3_2_1_2_1","first-page":"1","volume-title":"Proceedings of International Colloquium on Automata, Languages and Programming (ICALP)","author":"Abboud Amir","year":"2019","unstructured":"Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski, and Daniel Wolleb-Graf. Faster algorithms for all-pairs bounded min-cuts. In Proceedings of International Colloquium on Automata, Languages and Programming (ICALP), pages 7:1--7:15, 2019."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304207"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035315.ch36"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_3_2_1_6_1","first-page":"1","volume-title":"Proceedings of International Conference on Database Theory (ICDT)","author":"Alway Kaleb","year":"2021","unstructured":"Kaleb Alway, Eric Blais, and Semih Salihoglu. Box covers and domain orderings for beyond worst-case join processing. In Proceedings of International Conference on Database Theory (ICDT), pages 3:1--3:23, 2021."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514909"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_3_2_1_9_1","volume-title":"Decomposable searching problems. Information Processing Letters (IPL), 8(5):244--251","author":"Bentley Jon Louis","year":"1979","unstructured":"Jon Louis Bentley. Decomposable searching problems. Information Processing Letters (IPL), 8(5):244--251, 1979."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.110"},{"key":"e_1_3_2_1_11_1","first-page":"1","volume-title":"Computational Complexity Conference","author":"Bringmann Karl","unstructured":"Karl Bringmann, Nick Fischer, and Marvin Kunnemann. A fine-grained analogue of schaefer's theorem in P: dichotomy of exists?k-forall-quantified first-order graph properties. In Computational Complexity Conference, pages 31:1--31:27."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.36"},{"key":"e_1_3_2_1_13_1","first-page":"1","volume-title":"Proceedings of Annual Symposium on Combinatorial Pattern Matching (CPM)","author":"Bringmann Karl","year":"2017","unstructured":"Karl Bringmann and Philip Wellnitz. Clique-based lower bounds for parsing tree-adjoining grammars. In Proceedings of Annual Symposium on Combinatorial Pattern Matching (CPM), pages 12:1--12:14, 2017."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458331"},{"key":"e_1_3_2_1_15_1","first-page":"393","volume-title":"Proceedings of ACM Symposium on Principles of Database Systems (PODS)","author":"Carmeli Nofar","year":"2020","unstructured":"Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Benny Kimelfeld, and Nicole Schweikardt. Answering (unions of) conjunctive queries using random access and random-order enumeration. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 393--409, 2020."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.01.007"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.07.010"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304206"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00220-0"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035921"},{"key":"e_1_3_2_1_21_1","first-page":"1","volume-title":"Proceedings of International Conference on Database Theory (ICDT)","author":"Chen Yu","year":"2020","unstructured":"Yu Chen and Ke Yi. Random sampling and size estimation over cyclic joins. In Proceedings of International Conference on Database Theory (ICDT), pages 7:1--7:18, 2020."},{"key":"e_1_3_2_1_22_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2001","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. The MIT Press, 2001."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_3_2_1_24_1","first-page":"150","volume-title":"Proceedings of AAAI Conference on Artificial Intelligence (AAAI)","author":"Dechter Rina","year":"1988","unstructured":"Rina Dechter and Judea Pearl. Tree-clustering schemes for constraint-processing. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI), pages 150--154, 1988."},{"key":"e_1_3_2_1_25_1","first-page":"1","volume-title":"Proceedings of International Conference on Database Theory (ICDT)","volume":"186","author":"Deep Shaleen","unstructured":"Shaleen Deep, Xiao Hu, and Paraschos Koutris. Enumeration algorithms for conjunctive queries with projection. In Proceedings of International Conference on Database Theory (ICDT), volume 186, pages 14:1--14:17."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380607"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196979"},{"key":"e_1_3_2_1_28_1","volume-title":"On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science, 326(1--3):57--67","author":"Eisenbrand Friedrich","year":"2004","unstructured":"Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science, 326(1--3):57--67, 2004."},{"key":"e_1_3_2_1_29_1","first-page":"1","volume-title":"Proceedings of International Colloquium on Automata, Languages and Programming (ICALP)","author":"Fichtenberger Hendrik","year":"2020","unstructured":"Hendrik Fichtenberger, Mingze Gao, and Pan Peng. Sampling arbitrary subgraphs exactly uniformly in sublinear time. In Proceedings of International Colloquium on Automata, Languages and Programming (ICALP), pages 45:1--45:13, 2020."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2004.11920139"},{"key":"e_1_3_2_1_31_1","volume-title":"marshals, and guards: game theoretic and logical characterizations of hypertree width. Journal of Computer and System Sciences (JCSS), 66(4):775--808","author":"Gottlob Georg","year":"2003","unstructured":"Georg Gottlob, Nicola Leone, and Francesco Scarcello. Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width. Journal of Computer and System Sciences (JCSS), 66(4):775--808, 2003."},{"key":"e_1_3_2_1_32_1","volume-title":"Which arithmetic operations can be performed in constant time in the RAM model with addition? CoRR, abs\/2206.13851","author":"Grandjean Etienne","year":"2022","unstructured":"Etienne Grandjean and Louis Jachiet. Which arithmetic operations can be performed in constant time in the RAM model with addition? CoRR, abs\/2206.13851, 2022."},{"key":"e_1_3_2_1_33_1","first-page":"287","volume-title":"Proceedings of ACM Management of Data (SIGMOD)","author":"Peter","year":"1999","unstructured":"Peter J. Haas and Joseph M. Hellerstein. Ripple joins for online aggregation. In Proceedings of ACM Management of Data (SIGMOD), pages 287--298, 1999."},{"key":"e_1_3_2_1_34_1","first-page":"1","volume-title":"Symposium on Algorithmic Foundations of Dynamic Networks (SAND)","volume":"221","author":"Hanauer Kathrin","year":"2022","unstructured":"Kathrin Hanauer, Monika Henzinger, and Qi Cheng Hua. Fully dynamic four-vertex subgraph counting. In Symposium on Algorithmic Foundations of Dynamic Networks (SAND), volume 221, pages 18:1--18:17, 2022."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520036"},{"key":"e_1_3_2_1_36_1","volume-title":"Joins via geometric resolutions: Worst case and beyond. ACM Transactions on Database Systems (TODS), 41(4):22:1--22:45","author":"Khamis Mahmoud Abo","year":"2016","unstructured":"Mahmoud Abo Khamis, Hung Q. Ngo, Christopher Re, and Atri Rudra. Joins via geometric resolutions: Worst case and beyond. ACM Transactions on Database Systems (TODS), 41(4):22:1--22:45, 2016."},{"key":"e_1_3_2_1_37_1","volume-title":"Proceedings of ACM Symposium on Principles of Database Systems (PODS)","author":"Kim Kyoungmin","year":"2023","unstructured":"Kyoungmin Kim, Jaehyun Ha, George Fletcher, and Wook-Shin Han. Guaranteeing the ???(AGM\/OUT) runtime for uniform sampling and size estimation over joins. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), 2023."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457246"},{"key":"e_1_3_2_1_39_1","first-page":"615","volume-title":"Proceedings of ACM Management of Data (SIGMOD)","author":"Li Feifei","year":"2016","unstructured":"Feifei Li, Bin Wu, Ke Yi, and Zhuoyue Zhao. Wander join: Online aggregation via random walks. In Proceedings of ACM Management of Data (SIGMOD), pages 615--629, 2016."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00068"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.80"},{"key":"e_1_3_2_1_42_1","first-page":"1","volume-title":"Proceedings of International Conference on Database Theory (ICDT)","volume":"155","author":"Navarro Gonzalo","year":"2020","unstructured":"Gonzalo Navarro, Juan L. Reutter, and Javiel Rojas-Ledesma. Optimal joins using compact data structures. In Proceedings of International Conference on Database Theory (ICDT), volume 155, pages 21:1--21:21, 2020."},{"issue":"2","key":"e_1_3_2_1_43_1","first-page":"415","article-title":"On the complexity of the subgraph problem","volume":"26","author":"Nesetril Jaroslav","year":"1985","unstructured":"Jaroslav Nesetril and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415--419, 1985.","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594547"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_3_2_1_46_1","volume-title":"Worst-case optimal join algorithms. Journal of the ACM (JACM), 65(3):16:1--16:40","author":"Ngo Hung Q.","year":"2018","unstructured":"Hung Q. Ngo, Ely Porat, Christopher Re, and Atri Rudra. Worst-case optimal join algorithms. Journal of the ACM (JACM), 65(3):16:1--16:40, 2018."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_3_2_1_48_1","volume-title":"Proceedings of the VLDB Endowment (PVLDB), 6(14)","author":"Nirkhiwale Supriya","year":"1809","unstructured":"Supriya Nirkhiwale, Alin Dobra, and Christopher M. Jermaine. A sampling algebra for aggregate estimation. Proceedings of the VLDB Endowment (PVLDB), 6(14):1798--1809, 2013."},{"key":"e_1_3_2_1_49_1","volume-title":"Size bounds for factorised representations of query results. ACM Transactions on Database Systems (TODS), 40(1):2:1--2:44","author":"Olteanu Dan","year":"2015","unstructured":"Dan Olteanu and Jakub Zavodny. Size bounds for factorised representations of query results. ACM Transactions on Database Systems (TODS), 40(1):2:1--2:44, 2015."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1561\/1500000040"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457302"},{"key":"e_1_3_2_1_52_1","volume-title":"Intersection joins under updates. Journal of Computer and System Sciences (JCSS), 124:41--64","author":"Tao Yufei","year":"2022","unstructured":"Yufei Tao and Ke Yi. Intersection joins under updates. Journal of Computer and System Sciences (JCSS), 124:41--64, 2022."},{"key":"e_1_3_2_1_53_1","volume-title":"Efficient algorithms for clique problems. Information Processing Letters (IPL), 109(4):254--257","author":"Vassilevska Virginia","year":"2009","unstructured":"Virginia Vassilevska. Efficient algorithms for clique problems. Information Processing Letters (IPL), 109(4):254--257, 2009."},{"key":"e_1_3_2_1_54_1","first-page":"96","volume-title":"Proceedings of International Conference on Database Theory (ICDT)","author":"Veldhuizen Todd L.","year":"2014","unstructured":"Todd L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In Proceedings of International Conference on Database Theory (ICDT), pages 96--106, 2014."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824051"},{"key":"e_1_3_2_1_56_1","volume-title":"7th International Conference, September 9--11, 1981","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. Algorithms for acyclic database schemes. In Very Large Data Bases, 7th International Conference, September 9--11, 1981, Cannes, France, Proceedings, pages 82--94, 1981."},{"key":"e_1_3_2_1_57_1","first-page":"469","volume-title":"Proceedings of ACM Management of Data (SIGMOD)","author":"Yu Feng","year":"2013","unstructured":"Feng Yu, Wen-Chi Hou, Cheng Luo, Dunren Che, and Mengxia Zhu. CS2: a new database synopsis for query estimation. In Proceedings of ACM Management of Data (SIGMOD), pages 469--480, 2013."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183739"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389717"}],"event":{"name":"SIGMOD\/PODS '23: International Conference on Management of Data","location":"Seattle WA USA","acronym":"SIGMOD\/PODS '23","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584372.3588666","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3584372.3588666","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:28Z","timestamp":1750178788000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584372.3588666"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,18]]},"references-count":59,"alternative-id":["10.1145\/3584372.3588666","10.1145\/3584372"],"URL":"https:\/\/doi.org\/10.1145\/3584372.3588666","relation":{},"subject":[],"published":{"date-parts":[[2023,6,18]]},"assertion":[{"value":"2023-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}