{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:54:31Z","timestamp":1775638471607,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540602200","type":"print"},{"value":"9783540447474","type":"electronic"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60220-8_74","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:53:00Z","timestamp":1330278780000},"page":"334-345","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":94,"title":["The buffer tree: A new technique for optimal I\/O-algorithms"],"prefix":"10.1007","author":[{"given":"Lars","family":"Arge","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"29_CR1","first-page":"467","volume":"267","author":"A. Aggarwal","year":"1987","unstructured":"A. Aggarwal, J.S. Vitter: The I\/O Complexity of Sorting and Related Problems. In Proc. of 14th ICALP (1987), LNCS 267, 467\u2013478, and: The Input\/Output Complexity of Sorting and Related Problems. Communications of the ACM, Vol 31 (9) (1988), 1116\u20131127.","journal-title":"Proc. of 14th ICALP"},{"key":"29_CR2","doi-asserted-by":"crossref","unstructured":"L. Arge: External-Storage Data Structures for Plane-Sweep Algorithms. BRICS Report Series RS-94-16, University of Aarhus, June 1994.","DOI":"10.7146\/brics.v1i16.21651"},{"key":"29_CR3","first-page":"83","volume":"709","author":"L. Arge","year":"1993","unstructured":"L. Arge, M. Knudsen, K. Larsen: A General Lower Bound on the I\/O-Complexity of Comparison-based Algorithms. In Proc. of 3rd WADS (1993), LNCS 709, 83\u201394.","journal-title":"Proc. of 3rd WADS"},{"key":"29_CR4","unstructured":"L. Arge, D.E. Vengroff, J.S. Vitter: External-Memory Algorithms for Processing Line Segments in Geographic Information Systems. Manuscript."},{"key":"29_CR5","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1109\/TC.1980.1675628","volume":"29","author":"J.L. Bentley","year":"1980","unstructured":"J.L. Bentley, D. Wood: An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles. IEEE Transactions on Computers 29 (1980), 571\u2013577.","journal-title":"IEEE Transactions on Computers"},{"key":"29_CR6","unstructured":"Y-J. Chiang: Experiments on the Practical I\/O Efficiency of Geometric Algorithms: Distribution Sweep vs. Plane Sweep. These Proceedings."},{"key":"29_CR7","unstructured":"Y-J. Chiang, M.T. Goodrich, E.F. Grove, R. Tamassia, D.E. Vengroff, J.S. Vitter: External-Memory Graph Algorithms. In Proc. of 6th ACM-SIAM SODA (1995), 139\u2013149."},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"M.T. Goodrich, J. Tsay, D.E. Vengroff, J.S. Vitter: External-Memory Computational Geometry. In Proc. of 34th IEEE FOCS (1993), 714\u2013723.","DOI":"10.1109\/SFCS.1993.366816"},{"key":"29_CR9","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S. Huddleston","year":"1982","unstructured":"S. Huddleston, K. Mehlhorn: A New Data Structure for Representing Sorted Lists. Acta Informatica 17 (1982), 157\u2013184.","journal-title":"Acta Informatica"},{"key":"29_CR10","doi-asserted-by":"crossref","unstructured":"Ch. Icking, R. Klein, Th. Ottmann: Priority Search Trees in Secondary Memory. In Proc. of 1987 Graph-Theoretic Concepts in Computer Science, LNCS 314, 84\u201393.","DOI":"10.1007\/3-540-19422-3_7"},{"key":"29_CR11","doi-asserted-by":"crossref","unstructured":"P.C. Kanellakis, S. Ramaswamy, D.E. Vengroff, J.S. Vitter: Indexing for Data Models with Constraints and Classes. In Proc. 12th ACM PODS (1993), 233\u2013243.","DOI":"10.1145\/153850.153884"},{"key":"29_CR12","unstructured":"D.E. Knuth: The Art of Computer Programming, Vol 3: Sorting and Searching, Addison-Wesley (1973)."},{"key":"29_CR13","doi-asserted-by":"crossref","unstructured":"M.H. Nodine, J.S. Vitter: Deterministic Distribution Sort in Shared and Distributed Memory Multiprocessors. In Proc. of 5th ACM SPAA (1993).","DOI":"10.1145\/165231.165247"},{"key":"29_CR14","doi-asserted-by":"crossref","unstructured":"S. Ramaswamy, S. Subramanian: Path Caching: A Technique for Optimal External Searching. In Proc. 13th ACM PODS (1994), 25\u201335.","DOI":"10.1145\/182591.182595"},{"key":"29_CR15","unstructured":"S. Subramanian, S. Ramaswamy: The P-range Tree: A New Data Structure for Range Searching in Secondary Memory. In Proc. 6th ACM-SIAM SODA (1995), 378\u2013387."},{"issue":"3","key":"29_CR16","first-page":"15","volume":"27","author":"N.P. Yale","year":"1994","unstructured":"N.P. Yale: The I\/O Subsystem \u2014 A Candidate for Improvement. Guest Editor's Introduction in IEEE Computer 27 (3) (1994), 15\u201316.","journal-title":"Guest Editor's Introduction in IEEE Computer"},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"F. Preparata, M. Shamos: Computational Geometry, An Introduction. Text and Monographs in Computer Science, Springer-Verlag 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"29_CR18","doi-asserted-by":"crossref","unstructured":"C. Ruemmler, J. Wilkes: An Introduction to Disk Drive Modeling. IEEE Computer 27 (3) (1994).","DOI":"10.1109\/2.268881"},{"key":"29_CR19","unstructured":"M. Smid: Dynamic Data Structures on Multiple Storage Media. Ph.D thesis University of Amsterdam 1989."},{"key":"29_CR20","unstructured":"D.E. Vengroff: A Transparent Parallel I\/O Environment. In Proc. of 1994 DAGS Symposium on Parallel Computation."},{"key":"29_CR21","first-page":"26","volume":"480","author":"J.S. Vitter","year":"1991","unstructured":"J.S. Vitter: Efficient Memory Access in Large-Scale Computation (invited paper). In Proc. of 8th STACS (1991), LNCS 480, 26\u201341.","journal-title":"Proc. of 8th STACS"},{"key":"29_CR22","doi-asserted-by":"crossref","unstructured":"J.S. Vitter, E.A.M. Shriver: Algorithms for Parallel Memory I: Two-Level Memories. Algorithmica, 12 (2) (1994).","DOI":"10.1007\/BF01185207"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60220-8_74","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:55:57Z","timestamp":1742597757000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60220-8_74"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602200","9783540447474"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-60220-8_74","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}