{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:13Z","timestamp":1750309453860},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,3,8]],"date-time":"2013-03-08T00:00:00Z","timestamp":1362700800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,8]]},"DOI":"10.1007\/s00453-013-9763-6","type":"journal-article","created":{"date-parts":[[2013,3,7]],"date-time":"2013-03-07T21:19:50Z","timestamp":1362691190000},"page":"864-883","source":"Crossref","is-referenced-by-count":6,"title":["Cache-Oblivious Hashing"],"prefix":"10.1007","volume":"69","author":[{"given":"Rasmus","family":"Pagh","sequence":"first","affiliation":[]},{"given":"Zhewei","family":"Wei","sequence":"additional","affiliation":[]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[]},{"given":"Qin","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,3,8]]},"reference":[{"issue":"4","key":"9763_CR1","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1007\/s00454-011-9347-7","volume":"45","author":"P. Afshani","year":"2011","unstructured":"Afshani, P., Hamilton, C., Zeh, N.: Cache-oblivious range reporting with optimal queries requires superlinear space. Discrete Comput. Geom. 45(4), 824\u2013850 (2011)","journal-title":"Discrete Comput. Geom."},{"issue":"9","key":"9763_CR2","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"issue":"2","key":"9763_CR3","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/S0097539701389956","volume":"35","author":"M.A. Bender","year":"2005","unstructured":"Bender, M.A., Demaine, E.D., Farach-Colton, M.: Cache-oblivious B-trees. SIAM J. Comput. 35(2), 341\u2013358 (2005)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9763_CR4","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/s00453-010-9394-0","volume":"61","author":"M.A. Bender","year":"2010","unstructured":"Bender, M.A., Brodal, G.S., Fagerberg, R., Ge, D., He, S., Hu, H., Iacono, J., L\u00f3pez-Ortiz, A.: The cost of cache-oblivious searching. Algorithmica 61(2), 463\u2013505 (2010)","journal-title":"Algorithmica"},{"key":"9763_CR5","first-page":"307","volume-title":"Proc. ACM Symposium on Theory of Computing","author":"G.S. Brodal","year":"2003","unstructured":"Brodal, G.S., Fagerberg, R.: On the limits of cache-obliviousness. In: Proc. ACM Symposium on Theory of Computing, pp. 307\u2013315 (2003)"},{"key":"9763_CR6","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J. Carter","year":"1979","unstructured":"Carter, J., Wegman, M.: Universal classes of hash functions. J. Comput. Syst. Sci. 18, 143\u2013154 (1979)","journal-title":"J. Comput. Syst. Sci."},{"key":"9763_CR7","volume-title":"EEF Summer School on Massive Datasets","author":"E. Demaine","year":"2002","unstructured":"Demaine, E.: Cache-oblivious algorithms and data structures. In: EEF Summer School on Massive Datasets. Springer, Berlin (2002)"},{"issue":"3","key":"9763_CR8","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1145\/320083.320092","volume":"4","author":"R. Fagin","year":"1979","unstructured":"Fagin, R., Nievergelt, J., Pippenger, N., Strong, H.: Extendible hashing\u2014a fast access method for dynamic files. ACM Trans. Database Syst. 4(3), 315\u2013344 (1979)","journal-title":"ACM Trans. Database Syst."},{"key":"9763_CR9","first-page":"165","volume-title":"Proc. IEEE Symposium on Foundations of Computer Science","author":"M.L. Fredman","year":"1982","unstructured":"Fredman, M.L., Komlos, J., Szemeredi, E.: Storing a sparse table with o(1) worst -case access time. In: Proc. IEEE Symposium on Foundations of Computer Science, pp. 165\u2013170 (1982)"},{"key":"9763_CR10","first-page":"285","volume-title":"Proc. IEEE Symposium on Foundations of Computer Science","author":"M. Frigo","year":"1999","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: Proc. IEEE Symposium on Foundations of Computer Science, pp. 285\u2013298 (1999)"},{"issue":"1","key":"9763_CR11","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1145\/42267.42274","volume":"35","author":"G.H. Gonnet","year":"1988","unstructured":"Gonnet, G.H., Larson, P.-\u00c5.: External hashing with limited internal storage. J. ACM 35(1), 161\u2013184 (1988)","journal-title":"J. ACM"},{"issue":"2","key":"9763_CR12","volume":"33","author":"B. He","year":"2008","unstructured":"He, B., Luo, Q.: Cache-oblivious databases: limitations and opportunities. ACM Trans. Database Syst. 33(2), 8 (2008)","journal-title":"ACM Trans. Database Syst."},{"issue":"3","key":"9763_CR13","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/s00453-007-9155-x","volume":"52","author":"M.S. Jensen","year":"2008","unstructured":"Jensen, M.S., Pagh, R.: Optimality in external memory hashing. Algorithmica 52(3), 403\u2013411 (2008)","journal-title":"Algorithmica"},{"key":"9763_CR14","series-title":"The Art of Computer Programming","volume-title":"Sorting and Searching","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: Sorting and Searching. The Art of Computer Programming, vol. 3. Addison-Wesley, Reading (1973)"},{"issue":"4","key":"9763_CR15","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1145\/42404.42410","volume":"31","author":"P.-A. Larson","year":"1988","unstructured":"Larson, P.-A.: Dynamic hash tables. Commun. ACM 31(4), 446\u2013457 (1988)","journal-title":"Commun. ACM"},{"issue":"3","key":"9763_CR16","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1145\/44498.44500","volume":"13","author":"P.-A. Larson","year":"1988","unstructured":"Larson, P.-A.: Linear hashing with separators\u2014a dynamic hashing scheme achieving one-access retrieval. ACM Trans. Database Syst. 13(3), 366\u2013388 (1988)","journal-title":"ACM Trans. Database Syst."},{"key":"9763_CR17","first-page":"212","volume-title":"Proc. International Conference on Very Large Data Bases","author":"W. Litwin","year":"1980","unstructured":"Litwin, W.: Linear hashing: a new tool for file and table addressing. In: Proc. International Conference on Very Large Data Bases, pp. 212\u2013223 (1980)"},{"issue":"3","key":"9763_CR18","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1007\/BF02074879","volume":"32","author":"H.G. Mairson","year":"1992","unstructured":"Mairson, H.G.: The effect of table expansion on the program complexity of perfect hash functions. BIT Numer. Math. 32(3), 430\u2013440 (1992)","journal-title":"BIT Numer. Math."},{"key":"9763_CR19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"9763_CR20","doi-asserted-by":"crossref","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, 122\u2013144 (2004)","journal-title":"J. Algorithms"},{"issue":"3","key":"9763_CR21","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1137\/110827831","volume":"53","author":"A. Pagh","year":"2011","unstructured":"Pagh, A., Pagh, R., Ru\u017ei\u0107, M.: Linear probing with 5-wise independence. SIAM Rev. 53(3), 547\u2013558 (2011)","journal-title":"SIAM Rev."},{"key":"9763_CR22","unstructured":"Qi, H., Martel, C.U.: Design and analysis of hashing algorithms with cache effects. Technical report, UC, Davis (1998)"},{"key":"9763_CR23","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1137\/S089548019223872X","volume":"8","author":"J. Schmidt","year":"1995","unstructured":"Schmidt, J., Siegel, A., Srinivasan, A.: Chernoff\u2013Hoeffding bounds for applications with limited independence. SIAM J. Discrete Math. 8, 223 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"9763_CR24","volume-title":"Introduction to analytic and probabilistic number theory","author":"G. Tenenbaum","year":"1995","unstructured":"Tenenbaum, G.: Introduction to analytic and probabilistic number theory. Cambridge Univ. Press, Cambridge (1995)"},{"key":"9763_CR25","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1145\/1806689.1806752","volume-title":"Proc. ACM Symposium on Theory of Computing","author":"E. Verbin","year":"2010","unstructured":"Verbin, E., Zhang, Q.: The limits of buffering: a tight lower bound for dynamic membership in the external memory model. In: Proc. ACM Symposium on Theory of Computing, pp. 447\u2013456 (2010)"},{"issue":"3","key":"9763_CR26","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(81)90033-7","volume":"22","author":"M. Wegman","year":"1981","unstructured":"Wegman, M., Carter, J.: New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci. 22(3), 265\u2013279 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"9763_CR27","first-page":"253","volume-title":"Proc. ACM Symposium on Parallelism in Algorithms and Architectures","author":"Z. Wei","year":"2009","unstructured":"Wei, Z., Yi, K., Zhang, Q.: Dynamic external hashing: the limit of buffering. In: Proc. ACM Symposium on Parallelism in Algorithms and Architectures, pp. 253\u2013259 (2009)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9763-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9763-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9763-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:11Z","timestamp":1559137511000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9763-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,8]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["9763"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9763-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,8]]}}}