{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,22]],"date-time":"2026-10-22T11:41:29Z","timestamp":1792669289144,"version":"4.5.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2026,10,22]],"date-time":"2026-10-22T00:00:00Z","timestamp":1792627200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["882500"],"award-info":[{"award-number":["882500"]}]},{"name":"European Union\u2019s Horizon Europe research and innovation programme","award":["101093026"],"award-info":[{"award-number":["101093026"]}]},{"name":"DAIS\u2014Ca\u2019 Foscari University of Venice within the IRIDE program"},{"name":"pilot program Core Informatics at KIT (KiKIT) of the Helmholtz Association"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2026,10,31]]},"abstract":"<jats:p>\n                    A minimal perfect hash function (or MPHF) maps a set of\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( n \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    keys to\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\([n]:=\\{1,\\ldots,n\\}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    without collisions. Such functions find widespread application, e.g., in bioinformatics and databases. In this article, we revisit PTHash\u2014a construction technique particularly designed for fast queries. PTHash distributes the input keys into small buckets and, for each bucket, it searches for a hash function seed that places its keys in the output domain without collisions. The collection of all seeds is then stored in a compressed way. Since the first buckets are easier to place, buckets are considered in non-increasing order of size. Additionally, PTHash heuristically produces an imbalanced distribution of bucket sizes by distributing 60% of the keys into 30% of the buckets.\n                  <\/jats:p>\n                  <jats:p>\n                    Our main contribution is to characterize, up to lower-order terms, an\n                    <jats:italic toggle=\"yes\">optimal<\/jats:italic>\n                    choice for the expected bucket sizes, improving construction throughput for space efficient configurations both in theory and practice. Further contributions include a new encoding scheme for seeds that works across partitions of the data structure and a GPU parallelization.\n                  <\/jats:p>\n                  <jats:p>We call our technique PHOBIC\u2014Perfect Hashing with Optimized Bucket sizes and Interleaved Coding. Compared to PTHash, PHOBIC is 0.17\u2009bits\/key more space-efficient for same query time and construction throughput. For a configuration with fast queries, our GPU implementation can construct an MPHF at 2.17\u2009bits\/key in 28\u2009ns\/key, which can be queried in 37\u2009ns on the CPU.<\/jats:p>","DOI":"10.1145\/3849725","type":"journal-article","created":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T14:37:46Z","timestamp":1790260666000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["PHOBIC: Perfect Hashing with Optimized Bucket Sizes and Interleaved Coding"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9183-2926","authenticated-orcid":false,"given":"Stefan","family":"Hermann","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0474-1805","authenticated-orcid":false,"given":"Hans-Peter","family":"Lehmann","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0724-7092","authenticated-orcid":false,"given":"Giulio Ermanno","family":"Pibiri","sequence":"additional","affiliation":[{"name":"Ca\u2019 Foscari University of Venice, Venice, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3330-9349","authenticated-orcid":false,"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6477-0106","authenticated-orcid":false,"given":"Stefan","family":"Walzer","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,10,22]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15775-2_37"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_61"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2635816"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3596453"},{"key":"e_1_3_2_6_2","first-page":"1","volume-title":"ALENEX","author":"Beling Piotr","year":"2026","unstructured":"Piotr Beling and Peter Sanders. 2026. PHast\u2014Perfect hashing made fast. In ALENEX. SIAM, 1\u201314."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2023.19"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73951-7_13"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1093\/COMJNL\/BXH074"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0023501"},{"key":"e_1_3_2_12_2","first-page":"245","volume-title":"Proc. Amer. Math. Soc","volume":"121","author":"Choi K. P.","year":"1994","unstructured":"K. P. Choi. 1994. On the medians of gamma distributions and an equation of Ramanujan. Proc. Amer. Math. Soc. 121 (1994), 245\u2013251."},{"key":"e_1_3_2_13_2","unstructured":"Yann Collet. n.d. xxHash: Extremely Fast Non-Cryptographic Hash Algorithm. Retrieved from https:\/\/github.com\/Cyan4973\/xxHash"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1093\/BIOINFORMATICS\/BTY500"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976007.14"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/133160.133209"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-38851-9_23"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1966.1053907"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.SEA.2025.21"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","unstructured":"Khodor Hannoush Camille Marchet and Pierre Peterlongo. 2024. Cdbgtricks: Strategies to update a compacted de Bruijn graph. bioRxiv:2024.05.24.595676. 2024\u20132025. Retrieved from 10.1101\/2024.05.24.595676","DOI":"10.1101\/2024.05.24.595676"},{"key":"e_1_3_2_21_2","unstructured":"Stefan Hermann. 2024. PHOBIC-GPU. Retrieved from https:\/\/github.com\/stefanfred\/PHOBIC-GPU"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2025.9"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2025.99"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2024.69"},{"key":"e_1_3_2_25_2","unstructured":"Aaron Kiely. 2004. Selecting the Golomb Parameter in Rice Coding. IPN Progress Report 42 159."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3797036"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977561.CH15"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977929.15"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-025-01321-Z"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2025.109"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","unstructured":"Hans-Peter Lehmann. 2024. Fast and Space-Efficient Perfect Hashing. Ph.D. Dissertation. Karlsruher Institut f\u00fcr Technologie (KIT). DOI:10.5445\/IR\/1000176432","DOI":"10.5445\/IR\/1000176432"},{"key":"e_1_3_2_32_2","unstructured":"Hans-Peter Lehmann. 2024. MPHF Experiments\u2014GitHub. Retrieved from https:\/\/github.com\/ByteHamster\/MPHF-Experiments"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioadv\/vbag120"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.SEA.2017.25"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2006.261567"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107359949.008"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.80"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_12"},{"key":"e_1_3_2_39_2","first-page":"60","volume-title":"ALENEX","author":"Okanohara Daisuke","year":"2007","unstructured":"Daisuke Okanohara and Kunihiko Sadakane. 2007. Practical entropy-compressed rank\/select dictionary. In ALENEX. SIAM, 60\u201370."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btac245"},{"key":"e_1_3_2_41_2","unstructured":"Giulio Ermanno Pibiri. 2024. PTHash\/PHOBIC. Retrieved from https:\/\/github.com\/jermp\/pthash"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3404835.3462849"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3303341"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3077136.3080798"},{"key":"e_1_3_2_45_2","unstructured":"Robert F. Rice. 1979. Some Practical Universal Noiseless Coding Techniques. Technical Report."},{"key":"e_1_3_2_46_2","first-page":"313","volume-title":"EUROSIM","author":"Sanders Peter","year":"1994","unstructured":"Peter Sanders. 1994. Emulating MIMD Behaviour on SIMD-Machines. In EUROSIM. Elsevier, 313\u2013320."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3849725","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,22]],"date-time":"2026-10-22T11:09:14Z","timestamp":1792667354000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3849725"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,10,22]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,10,31]]}},"alternative-id":["10.1145\/3849725"],"URL":"https:\/\/doi.org\/10.1145\/3849725","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,10,22]]},"assertion":[{"value":"2025-03-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-09-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-10-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}