{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:24:45Z","timestamp":1777965885855,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540441809","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/3-540-45749-6_16","type":"book-chapter","created":{"date-parts":[[2007,7,4]],"date-time":"2007-07-04T15:42:44Z","timestamp":1183563764000},"page":"139-150","source":"Crossref","is-referenced-by-count":16,"title":["Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy"],"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":"Erik D.","family":"Demaine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"4Martin","family":"Farach-Colton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"9","key":"16_CR1","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"A. Aggarwal and J. S. Vitter. The input\/output complexity of sorting and related problems. CACM, 31(9):1116\u20131127, Sept. 1988.","journal-title":"CACM"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"L. Arge, M. A. Bender, E. D. Demaine, B. Holland-Minkley, and J. I. Munro. Cache-oblivious priority queue and graph algorithm applications. In STOC, 2002.","DOI":"10.1145\/509907.509950"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"M. A. Bender, R. Cole, E.D. Demaine, and M. Farach-Colton. Two simplified algorithms for maintaining order in a list. In ESA, 2002.","DOI":"10.1007\/3-540-45749-6_17"},{"key":"16_CR4","unstructured":"M. A. Bender, E. Demaine, and M. Farach-Colton. Cache-oblivious search trees. In FOCS, 2000."},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"M. A. Bender, E.D. Demaine, and M. Farach-Colton. Efficient tree layout in a multilevel memory hierarchy. In ESA, 2002.","DOI":"10.1007\/3-540-45749-6_18"},{"key":"16_CR6","unstructured":"M. A. Bender, Z. Duan, J. Iacono, and J. Wu. A locality-preserving cacheoblivious dynamic dictionary. In SODA, 2002."},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"G. S. Brodal, R. Fagerberg, and R. Jacob. Cache oblivious search trees via binary trees of small height (extended abstract). In SODA, 2002.","DOI":"10.7146\/brics.v8i36.21696"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"P. Dietz. Maintaining order in a linked list. In STOC, 1982.","DOI":"10.1145\/800070.802184"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"P. Dietz, J. I. Seiferas, and J. Zhang. At ight lower bound for on-line monotonic list labeling. In SWAT, 1994.","DOI":"10.1007\/3-540-58218-5_12"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"P. Dietz and J. Zhang. Lower bounds for monotonic list labeling. In SWAT, 1990.","DOI":"10.1007\/3-540-52846-6_87"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"P. F. Dietz and D.D. Sleator. Two algorithms for maintaining order in a list00. In STOC, 1987.","DOI":"10.1145\/28395.28434"},{"key":"16_CR12","unstructured":"M. Farach-Colton, P. Ferragina, and S. Muthukrishnan. Overcoming the memory bottleneck in suffix tree construction. In FOCS, 1998."},{"issue":"4","key":"16_CR13","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0020-0190(79)90060-7","volume":"9","author":"W.R. Franklin","year":"1979","unstructured":"W.R. Franklin. Padded lists: Set operations in expected O(log logN) time. IPL, 9(4):161\u2013166, 1979.","journal-title":"IPL"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In FOCS, 1999.","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"J. Gray and G. Graefe. The five minute rule ten years later. SIGMOD Record, 26(4), 1997.","DOI":"10.1145\/271074.271094"},{"key":"16_CR16","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1137\/0216069","volume":"16","author":"M. Hofri","year":"1987","unstructured":"M. Hofri and A.G. Konheim. Padded lists revisited. SICOMP, 16:1073, 1987.","journal-title":"SICOMP"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"A. Itai, A.G. Konheim, and M. Rodeh. A sparse table implementation of priority queues. In S. Even and O. Kariv, editors, ICALP, 1981.","DOI":"10.1007\/3-540-10843-2_34"},{"key":"16_CR18","unstructured":"R. Ladner, J. Fix, and A. LaMarca. Cache performance analysis of algorithms. In SODA, 1999."},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1006\/jagm.1998.0985","volume":"31","author":"A. LaMarca","year":"1999","unstructured":"A. LaMarca and R.E. Ladner. The influence of caches on the performance of sorting. Journal of Algorithms, 31:66\u2013104, 1999.","journal-title":"Journal of Algorithms"},{"key":"16_CR20","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(80)90132-5","volume":"10","author":"R. Melville","year":"1980","unstructured":"R. Melville and D. Gries. Controlled density sorting. IPL, 10:169\u2013172, 1980.","journal-title":"IPL"},{"key":"16_CR21","unstructured":"D. Patterson and K. Keeton. Hardware technology trends and database opportunities. In SIGMOD, 1998. Keynote address."},{"key":"16_CR22","unstructured":"H. Prokop. Cache-oblivious algorithms. Master\u2019s thesis, MIT, 1999."},{"key":"16_CR23","doi-asserted-by":"crossref","unstructured":"V. Raman. Locality preserving dictionaries: theory and application to clustering in databases. In PODS, 1999.","DOI":"10.1145\/303976.304009"},{"key":"16_CR24","unstructured":"S. Sen and S. Chatterjee. Towards a theory of cache-efficient algorithms. In SODA, 2000."},{"issue":"2","key":"16_CR25","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"D.D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. CACM, 28(2):202\u2013208, 1985.","journal-title":"CACM"},{"issue":"3","key":"16_CR26","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D.D. Sleator","year":"1985","unstructured":"D.D. Sleator and R. E. Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32(3):652\u2013686, July 1985.","journal-title":"Journal of the ACM"},{"issue":"1","key":"16_CR27","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF00289142","volume":"21","author":"A. Tsakalidis","year":"1984","unstructured":"A. Tsakalidis. Maintaining order in a generalized linked list. Acta Informatica, 21(1):101\u2013112, May 1984.","journal-title":"Acta Informatica"},{"key":"16_CR28","series-title":"Lect Notes Comput Sci","volume-title":"External memory algorithms","author":"J. S. Vitter","year":"1998","unstructured":"J. S. Vitter. External memory algorithms. LNCS, 1461, 1998."},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"D. E. Willard. Maintaining dense sequential files in a dynamic environment. In STOC, 1982.","DOI":"10.1145\/800070.802183"},{"key":"16_CR30","doi-asserted-by":"crossref","unstructured":"D. E. Willard. Good worst-case algorithms for inserting and deleting records in dense sequential files. In SIGMOD, 1986.","DOI":"10.1145\/16894.16879"},{"issue":"2","key":"16_CR31","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. Ad ensity control algorithm for doing insertions and deletions in a sequentially ordered file in good worst-case time. Information and Computation, 97(2):150\u2013204, Apr. 1992.","journal-title":"Information and Computation"},{"key":"16_CR32","unstructured":"J. Zhang. Density control and on-line labeling problems. Technical Report TR481, University of Rochester, Computer Science Department, Dec. 1993."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA 2002"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45749-6_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:10:38Z","timestamp":1605647438000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45749-6_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540441809"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-45749-6_16","relation":{},"subject":[]}}