{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T21:34:39Z","timestamp":1757540079151,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T00:00:00Z","timestamp":1560297600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T00:00:00Z","timestamp":1560297600000},"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,9]]},"DOI":"10.1007\/s00453-019-00595-4","type":"journal-article","created":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T07:51:52Z","timestamp":1560325912000},"page":"3707-3724","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Faster Algorithm for Cuckoo Insertion and Bipartite Matching in Large Graphs"],"prefix":"10.1007","volume":"81","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0319-3181","authenticated-orcid":false,"given":"Megha","family":"Khosla","sequence":"first","affiliation":[]},{"given":"Avishek","family":"Anand","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,6,12]]},"reference":[{"key":"595_CR1","doi-asserted-by":"crossref","unstructured":"Arbitman, Y., Naor, M., Segev, G.: De-amortized cuckoo hashing: Provable worst-case performance and experimental results. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming: Part I, ICALP \u201909, pp. 107\u2013118 (2009)","DOI":"10.1007\/978-3-642-02927-1_11"},{"key":"595_CR2","unstructured":"Aum\u00fcller, M., Dietzfelbinger, M., Woelfel, P.: A Simple hash class with strong randomness properties in graphs and hypergraphs. ArXiv e-prints (2016)"},{"key":"595_CR3","unstructured":"Cain, J.A., Sanders, P., Wormald, N.: The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation. In: Proceedings of the 18th annual ACM-SIAM symposium on Discrete algorithms (SODA 2007), pp. 469\u2013476 (2007)"},{"key":"595_CR4","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009). ISBN 0262033844, 9780262033848","edition":"3"},{"issue":"4","key":"595_CR5","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1002\/rsa.1011","volume":"18","author":"A Czumaj","year":"2001","unstructured":"Czumaj, A., Stemann, V.: Randomized allocation processes. Random Struct. Algorithms 18(4), 297\u2013331 (2001)","journal-title":"Random Struct. Algorithms"},{"key":"595_CR6","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Schellbach, U.: On risks of using cuckoo hashing with simple universal hash classes. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201909, pp. 795\u2013804 (2009)","DOI":"10.1137\/1.9781611973068.87"},{"key":"595_CR7","unstructured":"Fernholz, D., Ramachandran, V.: The k-orientability thresholds for $${G}_{n,p}$$. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 459\u2013468 (2007)"},{"key":"595_CR8","doi-asserted-by":"crossref","unstructured":"Fotakis, D., Pagh, R., Sanders, P., Spirakis, P.: Space efficient hash tables with worst case constant access time. In: STACS \u201903, volume 2607 of Lecture Notes in Computer Science, pp. 271\u2013282 (2003)","DOI":"10.1007\/3-540-36494-3_25"},{"issue":"3","key":"595_CR9","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":"6","key":"595_CR10","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":"3","key":"595_CR11","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1002\/rsa.20427","volume":"41","author":"A Frieze","year":"2012","unstructured":"Frieze, A., 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"},{"issue":"2","key":"595_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."},{"key":"595_CR13","unstructured":"Galassi, M., Davies, J., Theiler, J., Gough, B., Jungman, G., Booth, M., Rossi, F.: GNU scientific library reference manual. (2003). \n                    http:\/\/www.gnu.org\/software\/gsl"},{"issue":"4","key":"595_CR14","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n$$\\hat{~}$$5\/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"595_CR15","doi-asserted-by":"crossref","unstructured":"Khosla, M.: Balls into bins made faster. In: Algorithms\u2013ESA 2013, volume 8125 of Lecture Notes in Computer Science, pp. 601\u2013612 (2013)","DOI":"10.1007\/978-3-642-40450-4_51"},{"issue":"4","key":"595_CR16","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.1137\/080728743","volume":"39","author":"A Kirsch","year":"2009","unstructured":"Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: cuckoo hashing with a stash. SIAM J. Comput. 39(4), 1543\u20131561 (2009)","journal-title":"SIAM J. Comput."},{"key":"595_CR17","doi-asserted-by":"crossref","unstructured":"Lelarge, M.: A new approach to the orientation of random hypergraphs. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201912, pp. 251\u2013264 (2012)","DOI":"10.1137\/1.9781611973099.23"},{"key":"595_CR18","unstructured":"Mitzenmacher, M., Vadhan, S.: Why simple hash functions work: exploiting the entropy in a data stream. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201908, pp. 746\u2013755 (2008)"},{"key":"595_CR19","doi-asserted-by":"crossref","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. In: ESA \u201901, pp. 121\u2013133 (2001). ISBN 3-540-42493-8","DOI":"10.1007\/3-540-44676-1_10"},{"key":"595_CR20","unstructured":"Sanders, P., Egner, S., Korst, J.: Fast concurrent access to parallel disks. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), pp. 849\u2013858 (1999)"},{"key":"595_CR21","doi-asserted-by":"crossref","unstructured":"Schlegel, B., Gemulla, R., Lehner, W.: Fast integer compression using SIMD instructions. In: Workshop on Data Management on New Hardware (DaMoN 2010), pp. 34\u201340 (2010)","DOI":"10.1145\/1869389.1869394"},{"issue":"8","key":"595_CR22","doi-asserted-by":"publisher","first-page":"1801","DOI":"10.1109\/TKDE.2012.115","volume":"25","author":"A Zubiaga","year":"2013","unstructured":"Zubiaga, A., Fresno, V., Martinez, R., Garcia-Plaza, A.P.: Harnessing folksonomies to produce a social classification of resources. IEEE Trans. Knowl. Data Eng. 25(8), 1801\u20131813 (2013)","journal-title":"IEEE Trans. Knowl. Data Eng."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00595-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00595-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00595-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,10]],"date-time":"2020-06-10T23:24:20Z","timestamp":1591831460000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00595-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,12]]},"references-count":22,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["595"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00595-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,6,12]]},"assertion":[{"value":"23 November 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 June 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}