{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T08:42:16Z","timestamp":1769330536487,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":37,"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":"NSF","award":["III-1910014"],"award-info":[{"award-number":["III-1910014"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,18]]},"DOI":"10.1145\/3584372.3588675","type":"proceedings-article","created":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T22:21:22Z","timestamp":1685744482000},"page":"59-68","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Space-Time Tradeoffs for Conjunctive Queries with Access Patterns"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-7636-0831","authenticated-orcid":false,"given":"Hangdong","family":"Zhao","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2342-4060","authenticated-orcid":false,"given":"Shaleen","family":"Deep","sequence":"additional","affiliation":[{"name":"Microsoft Gray Systems Lab, Madison, WI, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6309-1702","authenticated-orcid":false,"given":"Paraschos","family":"Koutris","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,18]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"ICALP","author":"Afshani Peyman","year":"2016","unstructured":"Peyman Afshani and Jesper Asbj\u00f8rn Sindahl Nielsen. Data structure lower bounds for document indexing problems. In ICALP, 2016."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_5"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2011.5934973"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00558-9"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746568"},{"key":"e_1_3_2_1_8_1","volume-title":"Fast set intersection and two-patterns matching. Theoretical Computer Science, 411(40--42):3795--3800","author":"Cohen Hagai","year":"2010","unstructured":"Hagai Cohen and Ely Porat. Fast set intersection and two-patterns matching. Theoretical Computer Science, 411(40--42):3795--3800, 2010."},{"key":"e_1_3_2_1_9_1","volume-title":"On the hardness of distance oracle for sparse graph. arXiv preprint arXiv:1006.1117","author":"Cohen Hagai","year":"2010","unstructured":"Hagai Cohen and Ely Porat. On the hardness of distance oracle for sparse graph. arXiv preprint arXiv:1006.1117, 2010."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538788.1538810"},{"key":"e_1_3_2_1_11_1","first-page":"1","volume-title":"24th International Conference on Database Theory","author":"Deep Shaleen","year":"2021","unstructured":"Shaleen Deep, Xiao Hu, and Paraschos Koutris. Enumeration algorithms for conjunctive queries with projection. In 24th International Conference on Database Theory, page 1, 2021."},{"key":"e_1_3_2_1_12_1","volume-title":"Space-time tradeoffs for answering boolean conjunctive queries. arXiv preprint arXiv:2109.10889","author":"Deep Shaleen","year":"2021","unstructured":"Shaleen Deep, Xiao Hu, and Paraschos Koutris. Space-time tradeoffs for answering boolean conjunctive queries. arXiv preprint arXiv:2109.10889, 2021."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196979"},{"key":"e_1_3_2_1_14_1","volume-title":"26th International Conference on Database Theory, ICDT 2023","author":"Deng Shiyuan","year":"2023","unstructured":"Shiyuan Deng, Shangqi Lu, and Yufei Tao. Space-query tradeoffs in range sub-graph counting and listing. In 26th International Conference on Database Theory, ICDT 2023, March 28--31, 2023, Ioannina, Greece, pages 6:1--6:25, 2023."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62127-2_36"},{"key":"e_1_3_2_1_16_1","volume-title":"Treewidth and hyper-tree width. Tractability: Practical Approaches to Hard Problems, 1","author":"Gottlob Georg","year":"2014","unstructured":"Georg Gottlob, Gianluigi Greco, and Francesco Scarcello. Treewidth and hyper-tree width. Tractability: Practical Approaches to Hard Problems, 1, 2014."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-012-9129-8"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_3_2_1_19_1","volume-title":"ICDT","author":"Kara Ahmet","year":"2019","unstructured":"Ahmet Kara, Hung Q Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Counting triangles under updates in worst-case optimal time. In ICDT, 2019."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387646"},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the 26th International Conference on Database Theory (ICDT","author":"Kara Ahmet","year":"2023","unstructured":"Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Conjunctive queries with free access patterns under updates. In Proceedings of the 26th International Conference on Database Theory (ICDT 2023), 2022. The 26th International Conference on Database Theory, 2023, ICDT 2023 ; Conference date: 28-03--2023 Through 31-03--2023."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387645"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_53"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.03.026"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a005"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3003665.3003667"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.83"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448498"},{"key":"e_1_3_2_1_34_1","first-page":"1969","volume-title":"SIGMOD Conference","author":"Wang Yilei","year":"2021","unstructured":"Yilei Wang and Ke Yi. Secure yannakakis: Join-aggregate queries over private data. In SIGMOD Conference, pages 1969--1981. ACM, 2021."},{"key":"e_1_3_2_1_35_1","volume-title":"Extracting and analyzing hidden graphs from relational databases. CoRR, abs\/1701.07388","author":"Xirogiannopoulos Konstantinos","year":"2017","unstructured":"Konstantinos Xirogiannopoulos and Amol Deshpande. Extracting and analyzing hidden graphs from relational databases. CoRR, abs\/1701.07388, 2017."},{"key":"e_1_3_2_1_36_1","first-page":"82","volume-title":"VLDB","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. Algorithms for acyclic database schemes. In VLDB, pages 82--94. IEEE Computer Society, 1981."},{"key":"e_1_3_2_1_37_1","volume-title":"Space-time tradeoffs for conjunctive queries with access patterns. arXiv preprint arXiv:2304.06221","author":"Zhao Hangdong","year":"2023","unstructured":"Hangdong Zhao, Shaleen Deep, and Paraschos Koutris. Space-time tradeoffs for conjunctive queries with access patterns. arXiv preprint arXiv:2304.06221, 2023."}],"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.3588675","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/abs\/10.1145\/3584372.3588675","content-type":"text\/html","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3584372.3588675","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.3588675"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,18]]},"references-count":37,"alternative-id":["10.1145\/3584372.3588675","10.1145\/3584372"],"URL":"https:\/\/doi.org\/10.1145\/3584372.3588675","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"}}]}}