{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:55:07Z","timestamp":1787385307024,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540424932","type":"print"},{"value":"9783540446767","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44676-1_5","type":"book-chapter","created":{"date-parts":[[2007,5,18]],"date-time":"2007-05-18T16:43:15Z","timestamp":1179506595000},"page":"62-73","source":"Crossref","is-referenced-by-count":11,"title":["Duality between Prefetching and Queued Writing with Parallel Disks"],"prefix":"10.1007","author":[{"given":"David A.","family":"Hutchinson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"issue":"9","key":"5_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":"5_CR2","doi-asserted-by":"crossref","unstructured":"S. Albers, N. Garg, and S. Leonardi. Minimizing stall time in single and parallel disk systems. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC-98), pages 454\u2013462, New York, May 23\u201326 1998. ACM Press.","DOI":"10.1145\/276698.276858"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"R. D. Barve and J. S. Vitter. A simple and efficient parallel disk mergesort. In Proceedings of the 11th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 232\u2013241, St. Malo, France, June 1999.","DOI":"10.1145\/305619.305646"},{"issue":"4","key":"5_CR4","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1016\/S0167-8191(97)00015-X","volume":"23","author":"R. D. Barve","year":"1997","unstructured":"Rakesh D. Barve, Edward F. Grove, and Jeffrey Scott Vitter. Simple randomized mergesort on parallel disks. Parallel Computing, 23(4):601\u2013631, 1997.","journal-title":"Parallel Computing"},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1147\/sj.52.0078","volume":"5","author":"A. L. Belady","year":"1966","unstructured":"A. L. Belady. A study of replacement algorithms for virtual storage computers. IBM Systems Journal, 5:78\u2013101, 1966.","journal-title":"IBM Systems Journal"},{"key":"5_CR6","volume-title":"Online Computation and Competitive Analysis","author":"A. Borodin","year":"1998","unstructured":"Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, Cambridge, 1998."},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Pei Cao, Edward W. Felten, Anna R. Karlin, and Kai Li. Implementation and performance of integrated application-controlled file caching, prefetching and disk scheduling. ACM Transactions on Computer Systems, 14(4):311\u2013343, Nov. 1996.","DOI":"10.1145\/235543.235544"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"F. Dehne, W. Dittrich, and D. Hutchinson. Efficient external memory algorithms by simulating coarse-grained parallel algorithms. In Proceedings of the 9th ACM Symposium on Parallel Algorithms and Architectures, pages 106\u2013115, June 1997.","DOI":"10.1145\/258492.258503"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"F. Dehne, D. Hutchinson, and A. Maheshwari. Reducing I\/O complexity by simulating coarse grained parallel algorithms. In Proc. of the Intl. Parallel Processing Symmposium, pages 14\u201320, April 1999.","DOI":"10.1109\/IPPS.1999.760428"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"M. Kallahalla and P. J.Varman. Optimal read-once parallel disk scheduling. In IOPADS, pages 68\u201377, 1999.","DOI":"10.1145\/301816.301835"},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"M. Kallahalla and P.J. Varman. Optimal prefetching and caching for parallel I\/O systems. In Proc. of the ACM Symposium on Parallel Algorithms and Architectures, 2001. To appear.","DOI":"10.1145\/378580.378648"},{"issue":"4","key":"5_CR12","doi-asserted-by":"publisher","first-page":"1051","DOI":"10.1137\/S0097539797326976","volume":"29","author":"T. Kimbrel","year":"2000","unstructured":"Tracy Kimbrel and Anna R. Karlin. Near-optimal parallel prefetching and caching. SI AM Journal on Computing, 29(4):1051\u20131082, 2000.","journal-title":"SI AM Journal on Computing"},{"key":"5_CR13","unstructured":"D. E. Knuth. The Art of Computer Programming\u2014 Sorting and Searching, volume 3. Addison Wesley, 2nd edition, 1998."},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"M. H. Nodine and J. S. Vitter. Deterministic distribution sort in shared and distributed memory multiprocessors. In Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 120\u2013129, Velen, Germany, June-July 1993.","DOI":"10.1145\/165231.165247"},{"issue":"4","key":"5_CR15","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1145\/210332.210343","volume":"42","author":"M. H. Nodine","year":"1995","unstructured":"M. H. Nodine and J. S. Vitter. Greed Sort: An optimal sorting algorithm for multiple disks. Journal of the ACM, 42(4):919\u2013933, July 1995.","journal-title":"Journal of the ACM"},{"key":"5_CR16","unstructured":"P. Sanders, S. Egner, and J. Korst. Fast concurrent access to parallel disks. In 11th ACM-SIAM Symposium on Discrete Algorithms, pages 849\u2013858, 2000."},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"J. S. Vitter. External memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys, in press. An earlier version entitled \u201cExternal Memory Algorithms and Data Structures\u201d appeared in External Memory Algorithms and Visualization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1999, 1\u201338.","DOI":"10.1090\/dimacs\/050\/01"},{"key":"5_CR18","unstructured":"J. S. Vitter and D. A. Hutchinson. Distribution sort with randomized cycling. In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms, Washington, January 2001."},{"issue":"2\u20133","key":"5_CR19","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/BF01185207","volume":"12","author":"J. S. Vitter","year":"1994","unstructured":"J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory I: Two-level memories. Algorithmica, 12(2\u20133):110\u2013147, 1994.","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44676-1_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T12:18:56Z","timestamp":1737029936000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44676-1_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424932","9783540446767"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-44676-1_5","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}