{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:13:43Z","timestamp":1750220023230,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2022,12,13]],"date-time":"2022-12-13T00:00:00Z","timestamp":1670889600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>We consider the problem of querying the existence of hyperedges in hypergraphs. More formally, given a hypergraph, we need to answer queries of the form: \u201cDoes the following set of vertices form a hyperedge in the given hypergraph?\u201d Our aim is to set up data structures based on hashing to answer these queries as fast as possible. We propose an adaptation of a well-known perfect hashing approach for the problem at hand. We analyze the space and runtime complexity of the proposed approach and experimentally compare it with the state-of-the-art hashing-based solutions. Experiments demonstrate the efficiency of the proposed approach with respect to the state-of-the-art.<\/jats:p>","DOI":"10.1145\/3568421","type":"journal-article","created":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T11:03:53Z","timestamp":1667041433000},"page":"1-23","source":"Crossref","is-referenced-by-count":1,"title":["Algorithms and Data Structures for Hyperedge Queries"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0943-9314","authenticated-orcid":false,"given":"Jules","family":"Bertrand","sequence":"first","affiliation":[{"name":"ENS de Lyon, Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2260-2200","authenticated-orcid":false,"given":"Fanny","family":"Dufoss\u00e9","sequence":"additional","affiliation":[{"name":"Inria Grenoble, Rh\u00f4ne Alpes, Montbonnot-Saint-Martin, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7648-9979","authenticated-orcid":false,"given":"Somesh","family":"Singh","sequence":"additional","affiliation":[{"name":"Inria Lyon and LIP (UMR5668 Universit\u00e9 de Lyon-ENS de Lyon-UCBL-CNRS-Inria), Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4960-3545","authenticated-orcid":false,"given":"Bora","family":"U\u00e7ar","sequence":"additional","affiliation":[{"name":"CNRS and LIP (UMR5668 Universit\u00e9 de Lyon-ENS de Lyon-UCBL-CNRS-Inria), Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,12,13]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_2_2","DOI":"10.1145\/362686.362692"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_2","DOI":"10.1016\/j.is.2012.06.002"},{"doi-asserted-by":"publisher","key":"e_1_3_2_4_2","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"e_1_3_2_5_2","volume-title":"Introduction to Algorithms (3rd ed.)","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. 2009. Introduction to Algorithms (3rd ed.). The MIT Press, Cambridge, MA."},{"doi-asserted-by":"publisher","key":"e_1_3_2_6_2","DOI":"10.1145\/2049662.2049663"},{"doi-asserted-by":"publisher","key":"e_1_3_2_7_2","DOI":"10.1137\/S0097539791194094"},{"key":"e_1_3_2_8_2","series-title":"Proceedings of the 27th Annual European Symposium on Algorithms (ESA\u201919)","first-page":"38:1\u201338:16","volume":"144","author":"Dietzfelbinger M.","year":"2019","unstructured":"M. Dietzfelbinger and S. Walzer. 2019. Dense peelable random uniform hypergraphs. In Proceedings of the 27th Annual European Symposium on Algorithms (ESA\u201919)(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 144), M. A. Bender, O. Svensson, and G. Herman (Eds.). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 38:1\u201338:16."},{"unstructured":"P. C. Dillinger L. H\u00fcbschle-Schneider P. Sanders and S. Walzer. 2021. Fast Succinct Retrieval and Approximate Membership using Ribbon. Retrieved from https:\/\/arxiv.org\/abs\/2109.01892","key":"e_1_3_2_9_2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_10_2","DOI":"10.1137\/1.9781611976007.14"},{"doi-asserted-by":"publisher","key":"e_1_3_2_11_2","DOI":"10.1145\/828.1884"},{"doi-asserted-by":"publisher","key":"e_1_3_2_12_2","DOI":"10.1109\/IPDPSW52791.2021.00050"},{"doi-asserted-by":"publisher","key":"e_1_3_2_13_2","DOI":"10.1007\/978-3-319-38851-9_23"},{"doi-asserted-by":"publisher","key":"e_1_3_2_14_2","DOI":"10.1145\/3510449"},{"doi-asserted-by":"publisher","key":"e_1_3_2_15_2","DOI":"10.1145\/3053370"},{"doi-asserted-by":"publisher","key":"e_1_3_2_16_2","DOI":"10.1137\/19M1266265"},{"doi-asserted-by":"publisher","key":"e_1_3_2_17_2","DOI":"10.14778\/3303753.3303757"},{"doi-asserted-by":"publisher","key":"e_1_3_2_18_2","DOI":"10.1002\/spe.2689"},{"doi-asserted-by":"publisher","key":"e_1_3_2_19_2","DOI":"10.4230\/LIPIcs.SEA.2017.25"},{"doi-asserted-by":"publisher","key":"e_1_3_2_20_2","DOI":"10.1007\/978-3-319-07959-2_12"},{"doi-asserted-by":"publisher","key":"e_1_3_2_21_2","DOI":"10.1007\/3-540-44676-1_10"},{"unstructured":"G. E. Pibiri and R. Trani. 2021. Parallel and External-Memory Construction of Minimal Perfect Hash Functions with PTHash. Retrieved from https:\/\/arxiv.org\/abs\/2106.02350.","key":"e_1_3_2_22_2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_23_2","DOI":"10.1145\/3404835.3462849"},{"doi-asserted-by":"publisher","key":"e_1_3_2_24_2","DOI":"10.1145\/1498698.1594230"},{"doi-asserted-by":"publisher","key":"e_1_3_2_25_2","DOI":"10.5555\/3378988"},{"doi-asserted-by":"publisher","key":"e_1_3_2_26_2","DOI":"10.1109\/IPDPSW55747.2022.00056"},{"unstructured":"S. Smith J. W. Choi J. Li R. Vuduc J. Park X. Liu and G. Karypis. 2017. FROSTT: The Formidable Repository of Open Sparse Tensors and Tools. Retrieved from http:\/\/frostt.io\/.","key":"e_1_3_2_27_2"},{"unstructured":"M. Thorup. 2015. High-speed Hashing for Integers and Strings. Retrieved from https:\/\/arxiv.org\/abs\/1504.06804.","key":"e_1_3_2_28_2"},{"key":"e_1_3_2_29_2","volume-title":"Random hypergraphs for hashing-based data structures","author":"Walzer S.","year":"2020","unstructured":"S. Walzer. 2020. Random hypergraphs for hashing-based data structures. Ph.D. Dissertation. Technische Universit\u00e4t Ilmenau, Germany."},{"doi-asserted-by":"publisher","key":"e_1_3_2_30_2","DOI":"10.1137\/1.9781611976465.131"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3568421","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3568421","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:51:33Z","timestamp":1750182693000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3568421"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,13]]},"references-count":29,"alternative-id":["10.1145\/3568421"],"URL":"https:\/\/doi.org\/10.1145\/3568421","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2022,12,13]]}}}