{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T09:30:47Z","timestamp":1775899847498,"version":"3.50.1"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319388502","type":"print"},{"value":"9783319388519","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-38851-9_23","type":"book-chapter","created":{"date-parts":[[2016,5,31]],"date-time":"2016-05-31T11:33:54Z","timestamp":1464694434000},"page":"339-352","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Fast Scalable Construction of (Minimal Perfect Hash) Functions"],"prefix":"10.1007","author":[{"given":"Marco","family":"Genuzio","sequence":"first","affiliation":[]},{"given":"Giuseppe","family":"Ottaviano","sequence":"additional","affiliation":[]},{"given":"Sebastiano","family":"Vigna","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,6,1]]},"reference":[{"key":"23_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1007\/978-3-642-04128-0_66","volume-title":"Algorithms - ESA 2009","author":"M Aum\u00fcller","year":"2009","unstructured":"Aum\u00fcller, M., Dietzfelbinger, M., Rink, M.: Experimental variations of a theoretically good retrieval data structure. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 742\u2013751. Springer, Heidelberg (2009)"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Boldi, P., Ottaviano, G., Venturini, R., Vigna, S.: Cache-oblivious peeling of random hypergraphs. In: 2014 Data Compression Conference (DCC 2014), pp. 352\u2013361. IEEE (2014)","DOI":"10.1109\/DCC.2014.48"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Monotone minimal perfect hashing: searching a sorted table with \n                    \n                      \n                    \n                    $$O(1)$$\n                    \n                      \n                        \n                          O\n                          (\n                          1\n                          )\n                        \n                      \n                    \n                   accesses. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA), pp. 785\u2013794. ACM, New York (2009)","DOI":"10.1137\/1.9781611973068.86"},{"key":"23_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/978-3-642-15775-2_37","volume-title":"Algorithms \u2013 ESA 2010","author":"D Belazzougui","year":"2010","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Fast prefix search in little space, with applications. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol. 6346, pp. 427\u2013438. Springer, Heidelberg (2010)"},{"issue":"3","key":"23_CR5","first-page":"3.2:1","volume":"16","author":"D Belazzougui","year":"2011","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Theory and practice of monotone minimal perfect hashing. ACM J. Exp. Algorithm. 16(3), 3.2:1\u20133.2:26 (2011)","journal-title":"ACM J. Exp. Algorithm."},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1007\/978-3-642-04128-0_61","volume-title":"Algorithms - ESA 2009","author":"D Belazzougui","year":"2009","unstructured":"Belazzougui, D., Botelho, F.C., Dietzfelbinger, M.: Hash, displace, and compress. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 682\u2013693. Springer, Heidelberg (2009)"},{"key":"23_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1007\/978-3-642-23719-5_63","volume-title":"Algorithms \u2013 ESA 2011","author":"D Belazzougui","year":"2011","unstructured":"Belazzougui, D., Navarro, G.: Alphabet-independent compressed text indexing. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 748\u2013759. Springer, Heidelberg (2011)"},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Venturini, R.: Compressed static functions with applications. In: SODA, pp. 229\u2013240 (2013)","DOI":"10.1137\/1.9781611973105.17"},{"key":"23_CR9","doi-asserted-by":"crossref","unstructured":"Boldi, P., Marino, A., Santini, M., Vigna, S.: BUbiNG: massive crawling for the masses. In: Proceedings of the Companion Publication of the 23rd International Conference on World Wide Web Companion, WWW Companion 2014, pp. 227\u2013228. International World Wide Web Conferences Steering Committee (2014)","DOI":"10.1145\/2567948.2577304"},{"issue":"1","key":"23_CR10","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.is.2012.06.002","volume":"38","author":"FC Botelho","year":"2013","unstructured":"Botelho, F.C., Pagh, R., Ziviani, N.: Practical perfect hashing in nearly optimal space. Inf. Syst. 38(1), 108\u2013131 (2013)","journal-title":"Inf. Syst."},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"Carter, L., Floyd, R., Gill, J., Markowsky, G., Wegman, M.: Exact and approximate membership testers. In: Proceedings of Symposium on Theory of Computation (STOC 1978), pp. 59\u201365. ACM Press (1978)","DOI":"10.1145\/800133.804332"},{"key":"23_CR12","unstructured":"Chazelle, B., Kilian, J., Rubinfeld, R., Tal, A.: The Bloomier filter: an efficient data structure for static support lookup tables. In: Munro, J.I. (ed.) Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, pp. 30\u201339. SIAM (2004)"},{"key":"23_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/978-3-642-14165-2_19","volume-title":"Automata, Languages and Programming","author":"M Dietzfelbinger","year":"2010","unstructured":"Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R., Rink, M.: Tight thresholds for cuckoo hashing via XORSAT. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 213\u2013225. Springer, Heidelberg (2010)"},{"key":"23_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-540-70575-8_32","volume-title":"Automata, Languages and Programming","author":"M Dietzfelbinger","year":"2008","unstructured":"Dietzfelbinger, M., Pagh, R.: Succinct data structures for retrieval and approximate membership (extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 385\u2013396. Springer, Heidelberg (2008)"},{"issue":"3","key":"23_CR15","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1002\/rsa.20426","volume":"41","author":"N Fountoulakis","year":"2012","unstructured":"Fountoulakis, N., Panagiotou, K.: Sharp load thresholds for cuckoo hashing. Random Struct. Algorithms 41(3), 306\u2013333 (2012)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"23_CR16","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1002\/rsa.20427","volume":"41","author":"AM Frieze","year":"2012","unstructured":"Frieze, A.M., Melsted, P.: Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables. Random Struct. Algorithms 41(3), 334\u2013364 (2012)","journal-title":"Random Struct. Algorithms"},{"key":"23_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-642-30642-6_15","volume-title":"Computer Science \u2013 Theory and Applications","author":"A Goerdt","year":"2012","unstructured":"Goerdt, A., Falke, L.: Satisfiability thresholds beyond k\n          \n                    \n                      \n                    \n                    $$-$$\n                    \n                      \n                        -\n                      \n                    \n                  XORSAT. In: Hirsch, E.A., Karhum\u00e4ki, J., Lepist\u00f6, A., Prilutskii, M. (eds.) CSR 2012. LNCS, vol. 7353, pp. 148\u2013159. Springer, Heidelberg (2012)"},{"key":"23_CR18","unstructured":"Knuth, D.E.: The Art of Computer Programming. Pre-Fascicle 1A. Draft of Section 7.1.3: Bitwise Tricks and Techniques (2007)"},{"key":"23_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/3-540-38424-3_8","volume-title":"Advances in Cryptology - CRYPTO \u201990","author":"BA LaMacchia","year":"1991","unstructured":"LaMacchia, B.A., Odlyzko, A.M.: Solving large sparse linear systems over finite fields. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 109\u2013133. Springer, Heidelberg (1991)"},{"issue":"6","key":"23_CR20","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1093\/comjnl\/39.6.547","volume":"39","author":"BS Majewski","year":"1996","unstructured":"Majewski, B.S., Wormald, N.C., Havas, G., Czech, Z.J.: A family of perfect hashing methods. Comput. J. 39(6), 547\u2013554 (1996)","journal-title":"Comput. J."},{"key":"23_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/3-540-39757-4_20","volume-title":"Advances in Cryptology","author":"AM Odlyzko","year":"1985","unstructured":"Odlyzko, A.M.: Discrete logarithms in finite fields and their cryptographic significance. In: Beth, T., Cot, N., Ingemarsson, I. (eds.) EUROCRYPT 1984. LNCS, vol. 209, pp. 224\u2013314. Springer, Heidelberg (1985)"},{"key":"23_CR22","unstructured":"Rink, M.: Thresholds for matchings in random bipartite graphs with applications to hashing-based data structures. Ph.D. thesis, Technische Universit\u00e4t Ilmenau (2015)"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-38851-9_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T00:36:04Z","timestamp":1558312564000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-38851-9_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319388502","9783319388519"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-38851-9_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"1 June 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}