{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:09:57Z","timestamp":1725484197202},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438649"},{"type":"electronic","value":"9783540454656"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45465-9_18","type":"book-chapter","created":{"date-parts":[[2007,5,27]],"date-time":"2007-05-27T01:12:57Z","timestamp":1180228377000},"page":"195-207","source":"Crossref","is-referenced-by-count":26,"title":["Exponential Structures for Efficient Cache-Oblivious Algorithms"],"prefix":"10.1007","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Cole","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,25]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"A. Aggarwal and J. S. Vitter. The I\/O complexity of sorting and related problems. Communications of the ACM 31, 1116\u20131127, 1988.","journal-title":"Communications of the ACM"},{"key":"18_CR2","unstructured":"A. Ailamaki, D. J. DeWitt, M. D. Hill, and D. A. Wood. DBMSs on a Modern Processor: Where Does Time Go? In Proc. 25th VLDB Conference (1999), pp 266\u2013277."},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"A. Andersson. Faster Deterministic Sorting and Searching in Linear Space. In Proc. 37th IEEE FOCS (1996), pp. 135\u2013141.","DOI":"10.1109\/SFCS.1996.548472"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"A. Andersson and M. Thorup. Tight(er) worst-case bounds on dynamic searching and priority queues. In Proc. 31st ACM STOC (2000), pp. 335\u2013342.","DOI":"10.1145\/335305.335344"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"L. Arge. External memory data structures. In J. Abello, P. M. Pardalos, and M. G. C. Resende, eds, Handbook of Massive Data Sets. Kluwer Academic, 2002.","DOI":"10.1007\/978-1-4615-0005-6_9"},{"key":"18_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/3-540-60313-1_151","volume-title":"Proc. 6th European Symposium on Algorithms","author":"L. Arge","year":"1995","unstructured":"L. Arge, D. E. Vengroff and J. S. Vitter. External-Memory Algorithms for Processing Line Segments in Geographic Information Systems (Extended Abstract). In Proc. 6th European Symposium on Algorithms (1995), LNCS 979, 295\u2013310."},{"issue":"3","key":"18_CR7","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"R. Bayer and E. M. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1(3): 173\u2013189, February 1972.","journal-title":"Acta Informatica"},{"key":"18_CR8","unstructured":"M. A. Bender, E. Demaine and M. Farach-Colton Cache-oblivous B-trees. In Proc. 41st IEEE FOCS (2000), pp. 399\u2013409."},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"M. A. Bender, R. Cole and R. Raman. Exponential structures for efficient cache-oblivious algorithms. University of Leicester TR 2002\/19, 2002.","DOI":"10.1007\/3-540-45465-9_18"},{"key":"18_CR10","unstructured":"M. A. Bender, Z. Duan, J. Iacono and J. Wu. A locality-preserving cache-oblivious dynamic dictionary. In Proc. 13th ACM-SIAM SODA (2002), pp. 29\u201338."},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"R. D. Blumofe, M. Frigo, C. F. Joerg, C. E. Leiserson, and K. H. Randall. An analysis of dag-consistent distributed shared-memory algorithms. In Proc. 8th ACM SPAA, pp. 297\u2013308, 1996.","DOI":"10.1145\/237502.237574"},{"key":"18_CR12","unstructured":"G. S. Brodal, R. Fagerberg and R. Jacob. Cache-oblivious search trees via binary trees of small height. In Proc. 13th ACM-SIAM SODA (2002), pp. 39\u201348."},{"key":"18_CR13","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1137\/0209045","volume":"9","author":"M. R. Brown","year":"1980","unstructured":"M. R. Brown, R. E. Tarjan. A data structure for representing sorted lists. SIAM J. Comput. 9 (1980), pp. 594\u2013614.","journal-title":"SIAM J. Comput."},{"key":"18_CR14","unstructured":"M. T. Goodrich, J-J. Tsay, D. E. Vengroff and J. S. Vitter. External-Memory Computational Geometry (Preliminary Version). In Proc. 34th IEEE FOCS (1993), pp. 714\u2013723."},{"issue":"3","key":"18_CR15","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M. L. Fredman","year":"1993","unstructured":"M. L. Fredman and D. E. Willard. Surpassing the information theoretic bound with fusion trees. J. Comput. System Set, 47(3):424\u2013436, 1993.","journal-title":"J. Comput. System Set"},{"key":"18_CR16","unstructured":"M. Frigo, C. E. Leiserson, H. Prokop and S. Ramachandran Cache-oblivious algorithms. In Proc. 40th IEEE FOCS (1999), pp. 285\u2013298."},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn. Data structures and algorithms, 1. Sorting and searching. Springer, 1984.","DOI":"10.1007\/978-3-642-69672-5"},{"key":"18_CR18","unstructured":"H. Prokop. Cache-oblivious algorithms. MS Thesis, MIT, 1999."},{"key":"18_CR19","series-title":"Lect Notes Comput Sci","volume-title":"TR 00-02","author":"N. Rahman","year":"2000","unstructured":"N. Rahman and R. Raman. Adapting radix sort to the memory hierarchy. TR 00-02, King\u2019s College London, 2000. Prel. vers. in Proc. ALENEX 2000. 20. N. Rahman, R. Cole and R. Raman. Optimised predecessor data structures for internal memory. In Proc. 5th Workshop on Algorithm Engg., LNCS 2141, pp. 67\u201378, 2001."},{"key":"18_CR20","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Communications of the ACM 29, 1986, 669\u2013679.","journal-title":"Communications of the ACM"},{"key":"18_CR21","unstructured":"M. Thorup. Faster Deterministic Sorting and Priority Queues in Linear Space. Proc. 9th ACM-SIAM SODA (1998), pp. 550\u2013555."},{"issue":"4","key":"18_CR22","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1137\/S0895479896297744","volume":"18","author":"S. Toledo","year":"1997","unstructured":"S. Toledo. Locality of reference in LU decomposition with partial pivoting. SIAM Journal on Matrix Analysis and Applications, 18(4): 1065\u20131081, Oct. 1997.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"18_CR23","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"J. S. Vitter","year":"2001","unstructured":"J. S. Vitter. External memory algorithms and data structures: Dealing with MASSIVE data. ACM Computing Surveys 33 (2001) pp. 209\u2013271.","journal-title":"ACM Computing Surveys"},{"issue":"2","key":"18_CR24","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0890-5401(92)90034-D","volume":"97","author":"D. E. Willard","year":"1992","unstructured":"D. E. Willard. A density control algorithm for doing insertions and deletions in a sequentially ordered file in good worst-case time. Information and Computation, 97(2): 150\u2013204, 1992.","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45465-9_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T11:05:34Z","timestamp":1556449534000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45465-9_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438649","9783540454656"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-45465-9_18","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}