{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T02:44:59Z","timestamp":1761965099517,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2019,6,17]],"date-time":"2019-06-17T00:00:00Z","timestamp":1560729600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,17]],"date-time":"2019-06-17T00:00:00Z","timestamp":1560729600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s00453-019-00572-x","type":"journal-article","created":{"date-parts":[[2019,6,17]],"date-time":"2019-06-17T12:02:52Z","timestamp":1560772972000},"page":"3162-3185","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Dynamic Space Efficient Hashing"],"prefix":"10.1007","volume":"81","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9598-3609","authenticated-orcid":false,"given":"Tobias","family":"Maier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3330-9349","authenticated-orcid":false,"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6477-0106","authenticated-orcid":false,"given":"Stefan","family":"Walzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,6,17]]},"reference":[{"key":"572_CR1","first-page":"1","volume-title":"The Objective Method: Probabilistic Combinatorial Optimization and Local Weak Convergence","author":"D Aldous","year":"2004","unstructured":"Aldous, D., Michael Steele, J.: The Objective Method: Probabilistic Combinatorial Optimization and Local Weak Convergence, pp. 1\u201372. Springer, Berlin (2004)"},{"key":"572_CR2","doi-asserted-by":"crossref","unstructured":"Arbitman, Y., Naor, M., Segev, G.: De-amortized cuckoo hashing: provable worst-case performance and experimental results. In: 36th International Conference on Automata, Languages and Programming (ICALP), number 5555 in LNCS, pp. 107\u2013118. Springer (2009)","DOI":"10.1007\/978-3-642-02927-1_11"},{"key":"572_CR3","doi-asserted-by":"crossref","unstructured":"Celis, P., Larson, P.-A., Ian Munro, J: Robin hood hashing. In: 26th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 281\u2013288 (1985)","DOI":"10.1109\/SFCS.1985.48"},{"issue":"4","key":"572_CR4","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0020-0190(02)00500-8","volume":"86","author":"L Devroye","year":"2003","unstructured":"Devroye, L., Morin, P.: Cuckoo hashing: further analysis. Inf. Process. Lett. 86(4), 215\u2013219 (2003)","journal-title":"Inf. Process. Lett."},{"key":"572_CR5","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R., Rink, M.: Tight thresholds for cuckoo hashing via XORSAT. In: 27th International Conference on Automata, Languages and Programming (ICALP), pp. 213\u2013225 (2010)","DOI":"10.1007\/978-3-642-14165-2_19"},{"issue":"4","key":"572_CR6","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1137\/S0097539791194094","volume":"23","author":"M Dietzfelbinger","year":"1994","unstructured":"Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf\u00a0der Heide, F., Rohnert, H., Tarjan, R.E.: Dynamic perfect hashing: upper and lower bounds. SIAM J. Comput. 23(4), 738\u2013761 (1994)","journal-title":"SIAM J. Comput."},{"key":"572_CR7","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Mitzenmacher, M., Rink, M.: Cuckoo hashing with pages. In: 19th European Symposium on Algorithms (ESA), number 6942 in LNCS, pp. 615\u2013627. Springer (2011)","DOI":"10.1007\/978-3-642-23719-5_52"},{"key":"572_CR8","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Weidling, C.: Balanced allocation and dictionaries with tightly packed constant size bins. In: International Colloquium on Automata, Languages, and Programming, pp. 166\u2013178. Springer (2005)","DOI":"10.1007\/11523468_14"},{"issue":"1","key":"572_CR9","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2007.02.054","volume":"380","author":"M Dietzfelbinger","year":"2007","unstructured":"Dietzfelbinger, M., Weidling, C.: Balanced allocation and dictionaries with tightly packed constant size bins. Theor. Comput. Sci. 380(1), 47\u201368 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"572_CR10","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s00224-004-1195-x","volume":"38","author":"D Fotakis","year":"2005","unstructured":"Fotakis, D., Pagh, R., Sanders, P., Spirakis, P.: Space efficient hash tables with worst case constant access time. Theory Comput. Syst. 38(2), 229\u2013248 (2005)","journal-title":"Theory Comput. Syst."},{"issue":"6","key":"572_CR11","doi-asserted-by":"publisher","first-page":"2156","DOI":"10.1137\/100797503","volume":"42","author":"N Fountoulakis","year":"2013","unstructured":"Fountoulakis, N., Panagiotou, K., Steger, A.: On the insertion time of cuckoo hashing. SIAM J. Comput. 42(6), 2156\u20132181 (2013)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"572_CR12","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1137\/090770928","volume":"40","author":"A Frieze","year":"2011","unstructured":"Frieze, A., Melsted, P., Mitzenmacher, M.: An analysis of random-walk cuckoo hashing. SIAM J. Comput. 40(2), 291\u2013308 (2011)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"572_CR13","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1016\/0022-0000(78)90046-6","volume":"16","author":"LJ Guibas","year":"1978","unstructured":"Guibas, L.J., Szemeredi, E.: The analysis of double hashing. J. Comput. Syst. Sci. 16(2), 226\u2013274 (1978)","journal-title":"J. Comput. Syst. Sci."},{"key":"572_CR14","doi-asserted-by":"crossref","unstructured":"Kirsch, A., Mitzenmacher, M.: Less hashing, same performance: Building a better bloom filter. In 14th European Symposium on Algorithms (ESA), number 4168 in LNCS, pp. 456\u2013467. Springer (2006)","DOI":"10.1007\/11841036_42"},{"key":"572_CR15","unstructured":"Kirsch, A., Mitzenmacher, M.: Using a queue to de-amortize cuckoo hashing in hardware. In: 45th Annual Allerton Conference on Communication, Control, and Computing, vol.\u00a075 (2007)"},{"key":"572_CR16","volume-title":"The Art of Computer Programming Sorting and Searching","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming Sorting and Searching, vol. 3. Addison Wesley Longman Publishing Co., Inc., Boston (1998)"},{"key":"572_CR17","doi-asserted-by":"crossref","unstructured":"Lelarge, M.: A new approach to the orientation of random hypergraphs. In: Proc. 23rd SODA, pp. 251\u2013264 (2012)","DOI":"10.1137\/1.9781611973099.23"},{"key":"572_CR18","doi-asserted-by":"crossref","unstructured":"Li, X., Andersen, D.G., Kaminsky, M., Freedman, M.J.: Algorithmic improvements for fast concurrent cuckoo hashing. In: 9th European Conference on Computer Systems, EuroSys, pp. 27:1\u201327:14. ACM (2014)","DOI":"10.1145\/2592798.2592820"},{"key":"572_CR19","unstructured":"Maier, T., Sanders, P.: Dynamic space efficient hashing. In: 25th Annual European Symposium on Algorithms (ESA 2017), vol. \u00a087 of Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2017)"},{"issue":"10","key":"572_CR20","doi-asserted-by":"publisher","first-page":"1094","DOI":"10.1109\/71.963420","volume":"12","author":"M Mitzenmacher","year":"2001","unstructured":"Mitzenmacher, M.: The power of two choices in randomized load balancing. IEEE Trans Parallel Distrib. Syst. 12(10), 1094\u20131104 (2001)","journal-title":"IEEE Trans Parallel Distrib. Syst."},{"key":"572_CR21","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M.: Some open questions related to cuckoo hashing. In: 17th European Symposium on Algorithms (ESA), Vol. 5757 of LNCS, pp. 1\u201310. Springer (2009)","DOI":"10.1007\/978-3-642-04128-0_1"},{"key":"572_CR22","unstructured":"Mitzenmacher, M., Panagiotou, K., Walzer, S.: Load thresholds for cuckoo hashing with double hashing. In: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), volume 101 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 29:1\u201329:9. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2018)"},{"key":"572_CR23","doi-asserted-by":"crossref","unstructured":"Nguyen, N., Tsigas, P.: Lock-free cuckoo hashing. In: 34th IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 627\u2013636 (2014)","DOI":"10.1109\/ICDCS.2014.70"},{"issue":"2","key":"572_CR24","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51(2), 122\u2013144 (2004)","journal-title":"J. Algorithms"},{"key":"572_CR25","unstructured":"Walzer, S.: Load thresholds for cuckoo hashing with overlapping blocks. CoRR, abs\/1707.06855 (2017)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00572-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00572-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00572-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,15]],"date-time":"2020-06-15T23:23:59Z","timestamp":1592263439000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00572-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,17]]},"references-count":25,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["572"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00572-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,6,17]]},"assertion":[{"value":"22 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}