{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T13:36:39Z","timestamp":1770903399099,"version":"3.50.1"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T00:00:00Z","timestamp":1687737600000},"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":[[2023,12,31]]},"abstract":"<jats:p>\n            In this paper we study a\n            <jats:italic>\n              <jats:bold>fingerprint-based minimal perfect hash function<\/jats:bold>\n            <\/jats:italic>\n            (\n            <jats:bold>\n              <jats:italic>FMPH<\/jats:italic>\n            <\/jats:bold>\n            for short). While FMPH is not as space-efficient as some other minimal perfect hash functions (for example RecSplit, CHD, or PTHash), it has a number of practical advantages that make it worthy of consideration. FMPH is simple and quite fast to evaluate. Its construction requires very little auxiliary memory, takes a short time and, in addition, can be parallelized or carried out without holding keys in memory.\n          <\/jats:p>\n          <jats:p>\n            In this paper, we propose an effective method (called\n            <jats:bold>FMPHGO<\/jats:bold>\n            ) that reduces the size of FMPH, as well as a number of implementation improvements. In addition, we experimentally study FMPHGO performance and find the best values for its parameters. Our benchmarks show that with our method and an efficient structure to support the rank queries on a bit vector, the FMPH size can be reduced to about 2.1 bits\/key, which is close to the size achieved by state-of-the-art methods and noticeably larger only compared to RecSplit. FMPHGO preserves most of the FMPH advantages mentioned above, but significantly reduces its construction speed. However, FMPHGO\u2019s construction speed is still competitive with methods of similar space efficiency (like CHD or PTHash), and seems to be good enough for practical applications.\n          <\/jats:p>","DOI":"10.1145\/3596453","type":"journal-article","created":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T11:14:20Z","timestamp":1683976460000},"page":"1-16","source":"Crossref","is-referenced-by-count":4,"title":["Fingerprinting-based Minimal Perfect Hashing Revisited"],"prefix":"10.1145","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3048-3704","authenticated-orcid":false,"given":"Piotr","family":"Beling","sequence":"first","affiliation":[{"name":"Faculty of Mathematics and Computer Science, University of \u0141\u00f3d\u017a , Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,26]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_61"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.587"},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1007\/11427186_42","volume-title":"Experimental and Efficient Algorithms","author":"Botelho Fabiano C.","year":"2005","unstructured":"Fabiano C. Botelho, Yoshiharu Kohayakawa, and Nivio Ziviani. 2005. A practical minimal perfect hashing method. In Experimental and Efficient Algorithms, Sotiris E. Nikoletseas (Ed.). Springer, Berlin, Berlin, 488\u2013500."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73951-7_13"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0023501"},{"key":"e_1_3_2_7_2","volume-title":"What Every Programmer Should Know About Memory","author":"Drepper Ulrich","year":"2007","unstructured":"Ulrich Drepper. 2007. What Every Programmer Should Know About Memory."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976007.14"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/133160.133209"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0605009"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104517"},{"key":"e_1_3_2_12_2","first-page":"27","volume-title":"Poster Proceedings Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA\u201905) (Greece)","author":"Gonz\u00e1lez Rodrigo","year":"2005","unstructured":"Rodrigo Gonz\u00e1lez, Szymon Grabowski, Veli M\u00e4kinen, and Gonzalo Navarro. 2005. Practical implementation of rank and select queries. In Poster Proceedings Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA\u201905) (Greece). 27\u201338."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SEA.2017.25"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_12"},{"key":"e_1_3_2_15_2","article-title":"Parallel and external-memory construction of minimal perfect hash functions with PTHash","volume":"2106","author":"Pibiri Giulio Ermanno","year":"2021","unstructured":"Giulio Ermanno Pibiri and Roberto Trani. 2021. Parallel and external-memory construction of minimal perfect hash functions with PTHash. CoRR abs\/2106.02350 (2021). arXiv:2106.02350 https:\/\/arxiv.org\/abs\/2106.02350.","journal-title":"CoRR"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3404835.3462849"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90181-T"},{"key":"e_1_3_2_18_2","volume-title":"memusage(1) Linux User\u2019s Manual (5.13 ed.)","author":"Schiffer Peter","year":"2021","unstructured":"Peter Schiffer, Michael Kerrisk, and Jan Chaloupka. 2021. memusage(1) Linux User\u2019s Manual (5.13 ed.)."},{"key":"e_1_3_2_19_2","article-title":"wyhash","author":"Wang Yi","unstructured":"Yi Wang. [n. d.]. wyhash. https:\/\/github.com\/wangyi-fudan\/wyhash. [accessed 18 Jun. 2022].","journal-title":"https:\/\/github.com\/wangyi-fudan\/wyhash. [accessed 18 Jun. 2022]"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38527-8_15"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3596453","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3596453","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:48:00Z","timestamp":1750178880000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3596453"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,26]]},"references-count":19,"alternative-id":["10.1145\/3596453"],"URL":"https:\/\/doi.org\/10.1145\/3596453","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,26]]}}}