{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T09:47:06Z","timestamp":1756460826771,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602200"},{"type":"electronic","value":"9783540447474"}],"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_75","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:52:59Z","timestamp":1330278779000},"page":"346-357","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Experiments on the practical I\/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep"],"prefix":"10.1007","author":[{"given":"Yi-Jen","family":"Chiang","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"issue":"9","key":"30_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 input\/output complexity of sorting and related problems. Communications of the ACM, 31(9):1116\u20131127, 1988.","journal-title":"Communications of the ACM"},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"L. Arge. The buffer tree: A new technique for optimal I\/O-algorithms. In Proc. Workshop on Algorithms and Data Structures, 1995.","DOI":"10.1007\/3-540-60220-8_74"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"L. Arge, D. E. Vengroff, and J. S. Vitter. External-memory algorithms for processing line segments in geographic information systems. Manuscript, 1995.","DOI":"10.1007\/3-540-60313-1_151"},{"key":"30_CR4","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"R. Bayer and E. McCreight. Organization of large ordered indexes. Acta Inform., 1:173\u2013189, 1972.","journal-title":"Acta Inform."},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"P. Callahan, M. T. Goodrich, and K. Ramaiyer. Topology B-trees and their applications. In Proc. Workshop on Algorithms and Data Structures, 1995.","DOI":"10.1007\/3-540-60220-8_78"},{"key":"30_CR6","doi-asserted-by":"crossref","unstructured":"Y.-J. Chiang. Experiments on the practical I\/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep. Report CS-95-07, Comput. Sci. Dept., Brown Univ., 1995.","DOI":"10.1007\/3-540-60220-8_75"},{"key":"30_CR7","unstructured":"Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter. External-memory graph algorithms. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 139\u2013149, 1995."},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/356770.356776","volume":"11","author":"D. Comer","year":"1979","unstructured":"D. Comer. The ubiquitous B-tree. ACM Comput. Surv., 11:121\u2013137, 1979.","journal-title":"ACM Comput. Surv."},{"key":"30_CR9","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1990","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. The MIT Press, Cambridge, Mass., 1990."},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"E. Feuerstein and A. Marchetti-Spaccamela. Memory paging for connectivity and path problems in graphs. In Proc. Int. Symp. on Algorithms and Comp., 1993.","DOI":"10.1007\/3-540-57568-5_273"},{"key":"30_CR11","unstructured":"P. G. Franciosa and M. Talamo. Orders, implicit k-sets representation and fast halfplane searching. In Proc. Workshop on Orders, Algorithms and Applications (ORDAL '94), pages 117\u2013127, 1994."},{"key":"30_CR12","unstructured":"G. N. Frederickson. A data structure for dynamically maintaining rooted trees. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 175\u2013184, 1993."},{"key":"30_CR13","doi-asserted-by":"crossref","unstructured":"M. T. Goodrich, M. H. Nodine, and J. S. Vitter. Blocking for external graph searching. In Proc. ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Sys., pages 222\u2013232, 1993.","DOI":"10.1145\/153850.153880"},{"key":"30_CR14","doi-asserted-by":"crossref","unstructured":"M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter. External-memory computational geometry. In IEEE Foundations of Comp. Sci., pages 714\u2013723, 1993.","DOI":"10.1109\/SFCS.1993.366816"},{"key":"30_CR15","doi-asserted-by":"crossref","unstructured":"P. C. Kanellakis, S. Ramaswamy, D. E. Vengroff, and J. S. Vitter. Indexing for data models with constraints and classes. In Proc. ACM Symp. on Principles of Database Sys., pages 233\u2013243, 1993.","DOI":"10.1145\/153850.153884"},{"key":"30_CR16","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1137\/0220050","volume":"20","author":"C. M. Kenyon-Mathieu","year":"1991","unstructured":"C. M. Kenyon-Mathieu and J. S. Vitter. The maximum size of dynamic data structures. SIAM J. Comput, 20:807\u2013823, 1991.","journal-title":"SIAM J. Comput"},{"key":"30_CR17","unstructured":"M. H. Nodine and J. S. Vitter. Paradigms for optimal sorting with multiple disks. In Proc. of the 26th Hawaii Int. Conf. on Systems Sciences, January 1993."},{"key":"30_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: an Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, New York, NY, 1985."},{"key":"30_CR19","doi-asserted-by":"crossref","unstructured":"S. Ramaswamy and S. Subramanian. Path caching: A technique for optimal external searching. In Proc. ACM Symp. on Principles of Database Sys., pages 25\u201335, 1994.","DOI":"10.1145\/182591.182595"},{"key":"30_CR20","unstructured":"S. Subramanian and S. Ramaswamy. The P-range tree: A new data structure for range searching in secondary memory. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 378\u2013387, 1995."},{"key":"30_CR21","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF01530929","volume":"3","author":"J. D. Ullman","year":"1991","unstructured":"J. D. Ullman and M. Yannakakis. The input\/output complexity of transitive closure. Annals of Mathematics and Artificial Intellegence, 3:331\u2013360, 1991.","journal-title":"Annals of Mathematics and Artificial Intellegence"},{"key":"30_CR22","unstructured":"D. E. Vengroff. A transparent parallel I\/O environment. In Proc. 1994 DAGS Symposium on Parallel Computation, July 1994."},{"key":"30_CR23","unstructured":"D. E. Vengroff and J. S. Vitter. I\/O-efficient scientific computation using TPIE. Manuscript, 1995."},{"key":"30_CR24","doi-asserted-by":"crossref","unstructured":"J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory I: Two-level memories. Algorithmica, 12(2), 1994.","DOI":"10.1007\/BF01185207"},{"key":"30_CR25","doi-asserted-by":"crossref","unstructured":"B. Zhu. Further computational geometry in secondary memory. In Proc. Int. Symp. on Algorithms and Computation, 1994.","DOI":"10.1007\/3-540-58325-4_218"}],"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_75","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:56:16Z","timestamp":1742597776000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60220-8_75"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602200","9783540447474"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-60220-8_75","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}