{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:04Z","timestamp":1781078164490,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642348617","type":"print"},{"value":"9783642348624","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34862-4_15","type":"book-chapter","created":{"date-parts":[[2012,11,26]],"date-time":"2012-11-26T09:00:11Z","timestamp":1353920411000},"page":"203-218","source":"Crossref","is-referenced-by-count":9,"title":["Cache-Oblivious Dictionaries and Multimaps with Negligible Failure Probability"],"prefix":"10.1007","author":[{"given":"Michael T.","family":"Goodrich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel S.","family":"Hirschberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Justin","family":"Thaler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Andersson, A., Miltersen, P.B., Riis, S., Thorup, M.: Static Dictionaries on AC0 RAMs: Query Time $\\Theta(\\sqrt{\\log n\/\\log \\log n})$ is Necessary and Sufficient. In: Proc. of FOCS, pp. 441\u2013450 (1996)","DOI":"10.7146\/brics.v4i14.21678"},{"issue":"1-2","key":"15_CR2","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0304-3975(98)00172-8","volume":"215","author":"A. Andersson","year":"1999","unstructured":"Andersson, A., Miltersen, P.B., Thorup, M.: Fusion trees can be implemented with AC0 instructions only. Theoretical Computer Science\u00a0215(1-2), 337\u2013344 (1999)","journal-title":"Theoretical Computer Science"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/978-3-642-25591-5_40","volume-title":"Algorithms and Computation","author":"E. Angelino","year":"2011","unstructured":"Angelino, E., Goodrich, M.T., Mitzenmacher, M., Thaler, J.: External-Memory Multimaps. In: Asano, T., Nakano, S.-i., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol.\u00a07074, pp. 384\u2013394. Springer, Heidelberg (2011)"},{"key":"15_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-02927-1_11","volume-title":"Automata, Languages and Programming","author":"Y. Arbitman","year":"2009","unstructured":"Arbitman, Y., Naor, M., Segev, G.: De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 107\u2013118. Springer, Heidelberg (2009)"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Arbitman, Y., Naor, M., Segev, G.: Backyard cuckoo hashing: Constant worst-case operations with a succinct representation. In: Proc. of FOCS, pp. 787\u2013796 (2010)","DOI":"10.1109\/FOCS.2010.80"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Demaine, E.D., Farach-Colton, M.: Cache-oblivious b-trees. In: Proc. of FOCS, pp. 399\u2013409 (2000)","DOI":"10.1109\/SFCS.2000.892128"},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/s00236-004-0159-6","volume":"41","author":"G.S. Brodal","year":"2005","unstructured":"Brodal, G.S., Demaine, E.D., Munro, I.: Fast allocation and deallocation with an improved buddy system. Acta Inf.\u00a041, 273\u2013291 (2005)","journal-title":"Acta Inf."},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Jacob, R.: Cache oblivious search trees via binary trees of small height. In: Proc. of SODA, pp. 39\u201348 (2002)","DOI":"10.7146\/brics.v8i36.21696"},{"issue":"2.2","key":"15_CR9","first-page":"1","volume":"12","author":"G.S. Brodal","year":"2008","unstructured":"Brodal, G.S., Fagerberg, R., Vinther, K.: Engineering a cache-oblivious sorting algorithm. J. Exp. Algorithmics 12, 2.2:1\u20132.2:23 (2008)","journal-title":"J. Exp. Algorithmics"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"B\u00fcttcher, S., Clarke, C.L.A.: Indexing time vs. query time: trade-offs in dynamic information retrieval systems. In: Proc. of CIKM, pp. 317\u2013318 (2005)","DOI":"10.1145\/1099554.1099645"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"B\u00fcttcher, S., Clarke, C.L.A., Lushman, B.: Hybrid index maintenance for growing text collections. In: Proc. of SIGIR, pp. 356\u2013363 (2006)","DOI":"10.1145\/1148170.1148233"},{"key":"15_CR12","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Cutting, D., Pedersen, J.: Optimization for dynamic inverted index maintenance. In: Proc. of SIGIR, pp. 405\u2013411 (1990)","DOI":"10.1145\/96749.98245"},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M.L. Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. System Sci.\u00a047, 424\u2013436 (1993)","journal-title":"J. Comput. System Sci."},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: Proc. of FOCS, pp. 285\u2013298 (1999)","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"15_CR16","unstructured":"Goodrich, M.T., Hirschberg, D.S., Mitzenmacher, M., Thaler, J.: Fully de-amortized cuckoo hashing for cache-oblivious dictionaries and multimaps. CoRR, abs\/1107.4378 (2011)"},{"key":"15_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1007\/978-3-642-22012-8_46","volume-title":"Automata, Languages and Programming","author":"M.T. Goodrich","year":"2011","unstructured":"Goodrich, M.T., Mitzenmacher, M.: Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol.\u00a06756, pp. 576\u2013587. Springer, Heidelberg (2011)"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"Guo, R., Cheng, X., Xu, H., Wang, B.: Efficient on-line index maintenance for dynamic text collections by using dynamic balancing tree. In: Proc. of CIKM, pp. 751\u2013760 (2007)","DOI":"10.1145\/1321440.1321545"},{"key":"15_CR19","unstructured":"Kirsch, A., Mitzenmacher, M.: Using a queue to de-amortize cuckoo hashing in hardware. In: Proc. of 45th Allerton Conference, pp. 751\u2013758 (2007)"},{"key":"15_CR20","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.\u00a039, 1543\u20131561 (2009)","journal-title":"SIAM J. Comput."},{"key":"15_CR21","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.\u00a03. Addison-Wesley, Reading (1973)"},{"key":"15_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1386118.1386125","volume":"33","author":"N. Lester","year":"2008","unstructured":"Lester, N., Moffat, A., Zobel, J.: Efficient online index construction for text databases. ACM Trans. Database Syst. 33, 19:1\u201319:33 (2008)","journal-title":"ACM Trans. Database Syst."},{"issue":"4","key":"15_CR23","doi-asserted-by":"publisher","first-page":"916","DOI":"10.1016\/j.ipm.2005.09.005","volume":"42","author":"N. Lester","year":"2006","unstructured":"Lester, N., Zobel, J., Williams, H.: Efficient online index maintenance for contiguous inverted lists. Inf. Processing & Management\u00a042(4), 916\u2013933 (2006)","journal-title":"Inf. Processing & Management"},{"issue":"5","key":"15_CR24","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1016\/j.is.2006.06.001","volume":"32","author":"R.W. Luk","year":"2007","unstructured":"Luk, R.W., Lam, W.: Efficient in-memory extensible inverted file. Information Systems\u00a032(5), 733\u2013754 (2007)","journal-title":"Information Systems"},{"key":"15_CR25","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and computing - randomized algorithms and probabilistic analysis. Cambridge University Press (2005)","DOI":"10.1017\/CBO9780511813603"},{"key":"15_CR26","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"52","author":"R. Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.: Cuckoo hashing. Journal of Algorithms\u00a052, 122\u2013144 (2004)","journal-title":"Journal of Algorithms"},{"key":"15_CR27","doi-asserted-by":"crossref","unstructured":"Pagh, R., Wei, Z., Yi, K., Zhang, Q.: Cache-oblivious hashing. In: Proc. of PODS, pp. 297\u2013304 (2010)","DOI":"10.1145\/1807085.1807124"},{"key":"15_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/3-540-68535-9_4","volume-title":"Computing and Combinatorics","author":"S. Rao Kosaraju","year":"1998","unstructured":"Rao Kosaraju, S., Pop, M.: De-amortization of Algorithms. In: Hsu, W.-L., Kao, M.-Y. (eds.) COCOON 1998. LNCS, vol.\u00a01449, pp. 4\u201314. Springer, Heidelberg (1998)"},{"issue":"3","key":"15_CR29","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/S0097539701386216","volume":"33","author":"A. Siegel","year":"2004","unstructured":"Siegel, A.: On universal classes of extremely random constant-time hash functions. SIAM J. Comput.\u00a033(3), 505\u2013543 (2004)","journal-title":"SIAM J. Comput."},{"key":"15_CR30","unstructured":"Thorup, M.: On AC0 implementations of fusion trees and atomic heaps. In: Proc. of SODA, pp. 699\u2013707 (2003)"},{"key":"15_CR31","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1137\/S0097539797322425","volume":"29","author":"D.E. Willard","year":"1999","unstructured":"Willard, D.E.: Examining computational geometry, van emde boas trees, and hashing from the perspective of the fusion tree. SIAM J. Comput.\u00a029, 1030\u20131049 (1999)","journal-title":"SIAM J. Comput."},{"key":"15_CR32","doi-asserted-by":"crossref","unstructured":"Zobel, J., Moffat, A.: Inverted files for text search engines. ACM Comput. Surv. 38 (July 2006)","DOI":"10.1145\/1132956.1132959"}],"container-title":["Lecture Notes in Computer Science","Design and Analysis of Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34862-4_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T20:38:47Z","timestamp":1745354327000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34862-4_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642348617","9783642348624"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34862-4_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}