{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:45:59Z","timestamp":1725558359376},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405450"},{"type":"electronic","value":"9783540450788"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45078-8_11","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T21:23:52Z","timestamp":1277241832000},"page":"114-126","source":"Crossref","is-referenced-by-count":13,"title":["Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees"],"prefix":"10.1007","author":[{"given":"Gianni","family":"Franceschini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)"},{"key":"11_CR2","first-page":"560","volume-title":"37th Annual Symposium on Foundations of Computer Science","author":"L. Arge","year":"1996","unstructured":"Arge, L., Vitter, J.S.: Optimal dynamic interval management in external memory. In: IEEE (ed.) 37th Annual Symposium on Foundations of Computer Science. Burlington, Vermontl, USA, October 14-16, pp. 560\u2013569. IEEE Computer Society Press, Los Alamitos (1996)"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1109\/SFCS.2000.892128","volume-title":"41st Annual Symposium on Foundations of Computer Science: proceedings: 12\u201314 November, 2000","author":"M.A. Bender","year":"2000","unstructured":"Bender, M.A., Demaine, E.D., Farach-Colton, M.: Cache-oblivious B-trees. In: IEEE (ed.) 41st Annual Symposium on Foundations of Computer Science: proceedings: Redondo Beach, California, USA, 12-14 November, pp. 399\u2013409. IEEE Computer Society Press, Los Alamitos (2000)"},{"key":"11_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/3-540-45465-9_18","volume-title":"Automata, Languages and Programming","author":"M.A. Bender","year":"2002","unstructured":"Bender, M.A., Cole, R., Raman, R.: Exponential structures for efficient cache-oblivious algorithms. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 195\u2013206. Springer, Heidelberg (2002)"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Jacob, R.: Cache-oblivious search trees via trees of small height. In: Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 39\u201348 (2002)","DOI":"10.7146\/brics.v8i36.21696"},{"key":"11_CR6","first-page":"365","volume-title":"Proceedings of the 19th Annual ACM Symposium on Theory of Computing","author":"P. Dietz","year":"1987","unstructured":"Dietz, P., Sleator, D.: Two algorithms for maintaining order in a list. In: Aho, A. (ed.) Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp. 365\u2013372. ACM Press, New York (1987)"},{"key":"11_CR7","first-page":"670","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003)","author":"G. Franceschini","year":"2003","unstructured":"Franceschini, G., Grossi, R.: Implicit dictionaries supporting searches and amortized updates in O(log n log log n). In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pp. 670\u2013678. SIAM, Philadelphia (2003)"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Franceschini, G., Grossi, R.: Optimal cache-oblivious implicit dictionaries. In: International Colloquium on Automata, Languages and Programming, LNCS (2003)","DOI":"10.1007\/3-540-45061-0_27"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Franceschini, G., Grossi, R.: Optimal implicit and cache-oblivious dictionaries over unbounded universes (2003) Full version","DOI":"10.1007\/3-540-45061-0_27"},{"key":"11_CR10","unstructured":"Franceschini, G., Grossi, R.: Optimal space-time dictionaries over an unbounded universe with flat implicit trees. Technical report TR-03-03, January 30 (2003)"},{"key":"11_CR11","unstructured":"Franceschini, G., Grossi, R., Ian Munro, J., Pagli, L.: Implicit Btrees: New results for the dictionary problem. In: IEEE Symposium on Foundations of Computer Science, FOCS (2002)"},{"issue":"1","key":"11_CR12","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1145\/322358.322364","volume":"30","author":"G.N. Frederickson","year":"1983","unstructured":"Frederickson, G.N.: Implicit data structures for the dictionary problem. Journal of the ACM\u00a030(1), 80\u201394 (1983)","journal-title":"Journal of the ACM"},{"key":"11_CR13","first-page":"285","volume-title":"40th Annual Symposium on Foundations of Computer Science: October 17\u201319, 1999","author":"M. Frigo","year":"1999","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: IEEE (ed.) 40th Annual Symposium on Foundations of Computer Science. New York City, New York, USA, 1109 Spring Street, Suite 300, Silver Spring, MD 20910, October 17-19, pp. 285\u2013297. IEEE Computer Society Press, Los Alamitos (1999)"},{"key":"11_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/3-540-10843-2_34","volume-title":"International Colloquium on Automata, Languages and Programming","author":"A. Itai","year":"1981","unstructured":"Itai, A., Konheim, A.G., Rodeh, M.: A sparse table implementation of priority queues. In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol.\u00a0115, pp. 417\u2013431. Springer, Heidelberg (1981)"},{"key":"11_CR15","volume-title":"The Art of Computer Programming III: Sorting and Searching","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: The Art of Computer Programming III: Sorting and Searching. Addison\u2013Wesley, Reading (1973)"},{"issue":"1","key":"11_CR16","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/0022-0000(86)90043-7","volume":"33","author":"J. Ian Munro","year":"1986","unstructured":"Ian Munro, J.: An implicit data structure supporting insertion, deletion, and search in O(log2 n) time. Journal of Computer and System Sciences\u00a033(1), 66\u201374 (1986)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"11_CR17","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/0022-0000(80)90037-9","volume":"21","author":"J.I. Munro","year":"1980","unstructured":"Ian Munro, J., Suwanda, H.: Implicit data structures for fast search and update. Journal of Computer and System Sciences\u00a021(2), 236\u2013250 (1980)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"11_CR18","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0890-5401(92)90034-D","volume":"97","author":"D.E. Willard","year":"1992","unstructured":"Willard, D.E.: A density control algorithm for doing insertions and deletions in a sequentially ordered file in good worst-case time. Information and Computation\u00a097(2), 150\u2013204 (1992)","journal-title":"Information and Computation"},{"key":"11_CR19","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J.W.J. Williams","year":"1964","unstructured":"Williams, J.W.J.: Algorithm 232: Heapsort. Communications of the ACM\u00a07, 347\u2013348 (1964)","journal-title":"Communications of the ACM"},{"key":"11_CR20","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"A.C. Yao","year":"1984","unstructured":"Yao, A.C.: Should tables be sorted? J. Assoc. Comput. Mach.\u00a031, 245\u2013281 (1984)","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45078-8_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T00:15:02Z","timestamp":1635552902000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45078-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405450","9783540450788"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45078-8_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}