{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T05:19:41Z","timestamp":1737609581617,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540676904"},{"type":"electronic","value":"9783540449850"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44985-x_38","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T20:17:33Z","timestamp":1194985053000},"page":"448-461","source":"Crossref","is-referenced-by-count":0,"title":["I\/O-Space Trade-Offs"],"prefix":"10.1007","author":[{"given":"Lars","family":"Arge","sequence":"first","affiliation":[]},{"given":"Jakob","family":"Pagter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,3,15]]},"reference":[{"key":"38_CR1","doi-asserted-by":"crossref","unstructured":"M. Adler. New coding techniques for improved bandwidth utilization. In Proc. 37th Annual Symposium on Foundations of Computer Science, pages 173\u2013182, 1996.","DOI":"10.1109\/SFCS.1996.548476"},{"issue":"9","key":"38_CR2","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":"38_CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai. Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions. In Proc. Thirty-First ACM Symposium on Theory of Computing, 1999.","DOI":"10.1145\/301250.301424"},{"key":"38_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1007\/3-540-60220-8_74","volume-title":"Proc. Workshop on Algorithms and Data Structures","author":"L. Arge","year":"1995","unstructured":"L. Arge. The Buffer Tree: A New Technique for Optimal I\/O-Algorithms. In Proc. Workshop on Algorithms and Data Structures, LNCS 955, pages 334\u2013345, 1995. A complete version appears as BRICS technical report RS-96-28, University of Aarhus."},{"key":"38_CR5","unstructured":"L. Arge. Efficient External-Memory Data Structures and Applications. PhD thesis, University of Aarhus, 1996."},{"key":"38_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/3-540-57155-8_238","volume-title":"Proc. of the Workshop on Algorithms and Datastructures","author":"L. Arge","year":"1993","unstructured":"L. Arge, M. Knudsen, and K. Larsen. A General Lower Bound on the I\/O-Complexity of Comparison-based Algorithms. In Proc. of the Workshop on Algorithms and Datastructures, LNCS 709, pages 83\u201394, 1993."},{"key":"38_CR7","doi-asserted-by":"crossref","unstructured":"L. Arge and P. B. Miltersen. On showing lower bounds for external-memory computational geometry problems. In J. Abello and J. S. Vitter, editors, External Memory Algorithms and Visualization. AMS Press, 1999.","DOI":"10.1090\/dimacs\/050\/08"},{"key":"38_CR8","volume-title":"Technical Report BRICS-RS-00-7","author":"L. Arge","year":"2000","unstructured":"L. Arge and J. Pagter. I\/O-Space Trade-Offs. Technical Report BRICS-RS-00-7, BRICS, University of Aarhus, Denmark, April 2000. Available via http:\/\/www.brics.dk."},{"key":"38_CR9","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1137\/0220017","volume":"20","author":"P. Beame","year":"1991","unstructured":"P. Beame. A General Sequential Time-Space Tradeoff for Finding Unique Elements. SIAM Journal on Computing, 20:270\u2013277, 1991.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"38_CR10","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0211022","volume":"11","author":"A. Borodin","year":"1982","unstructured":"A. Borodin and S. Cook. A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. SIAM Journal on Computing, 11(2):287\u2013297, 1982.","journal-title":"SIAM Journal on Computing"},{"key":"38_CR11","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1137\/0216007","volume":"16","author":"A. Borodin","year":"1987","unstructured":"A. Borodin, F. E. Fich, F. Meyer auf der Heide, E. Upfal, and A. Wigderson. A Time-Space Tradeoff for Element Distinctness. SIAM Journal on Computing, 16:97\u201399, 1987.","journal-title":"SIAM Journal on Computing"},{"key":"38_CR12","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/0022-0000(81)90037-4","volume":"22","author":"A. Borodin","year":"1981","unstructured":"A. Borodin, M. J. Fischer, D. G. Kirkpatrick, N. A. Lynch, and M. Tompa. A Time-Space Tradeoff for Sorting on Non-Oblivious Machines. Journal of Computer and System Sciences, 22:351\u2013364, 1981.","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR13","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0022-0000(87)90002-X","volume":"34","author":"G. N. Frederickson","year":"1987","unstructured":"G. N. Frederickson. Upper Bounds for Time-Space Trade-offs in Sorting and Selection. Journal of Computer and Systems Sciences, 34:19\u201326, 1987.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"38_CR14","doi-asserted-by":"crossref","unstructured":"J. W. Hong and H. T. Kung. I\/O complexity: The red-blue pebble game. In Proc. ACM Symp. on Theory of Computation, pages 326\u2013333, 1981.","DOI":"10.1145\/800076.802486"},{"key":"38_CR15","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(86)90150-7","volume":"47","author":"M. Karchmer","year":"1986","unstructured":"M. Karchmer. Two Time-Space Tradeoffs for Element Distinctness. Theoretical Computer Science, 47:237\u2013246, 1986.","journal-title":"Theoretical Computer Science"},{"key":"38_CR16","unstructured":"D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, 2nd edition, 1998."},{"issue":"107","key":"38_CR17","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0304-3975(93)90257-T","volume":"107","author":"Y. Mansour","year":"1993","unstructured":"Y. Mansour, N. Nisan, and P. Tiwari. The Computational Complexity of Universal Hashing. Theoretical Computer Science, (107):121\u2013133, 1993.","journal-title":"Theoretical Computer Science"},{"key":"38_CR18","unstructured":"K. Munagala and A. Ranade. I\/O-complexity of graph algorithm. In Proc. Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 687\u2013694, 1999."},{"key":"38_CR19","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"J. I. Munro","year":"1980","unstructured":"J. I. Munro and M. S. Paterson. Selection and Sorting with Limited Storage. Theoretical Computer Science, 12:315\u2013323, 1980.","journal-title":"Theoretical Computer Science"},{"key":"38_CR20","doi-asserted-by":"crossref","unstructured":"J. Pagter and T. Rauhe. Optimal Time-Space Trade-Offs for Sorting. In proc. 39th Annual Symposium on Foundations of Computer Science, pages 264\u2013268, 1998.","DOI":"10.1109\/SFCS.1998.743455"},{"key":"38_CR21","unstructured":"J. E. Savage. Models of Computation. Addison-Wesley, 1998."},{"key":"38_CR22","unstructured":"M. Tompa. Time-Space Tradeoffs for Straight-Line and Branching Programs. Technical Report 122\/78, Department of Computer Science, University of Toronto, July 1978. Ph.D. Thesis."},{"key":"38_CR23","doi-asserted-by":"crossref","unstructured":"J. S. Vitter. External memory algorithms and data structures. In J. Abello and J. S. Vitter, editors, External Memory Algorithms and Visualization. AMS Press, 1999.","DOI":"10.1090\/dimacs\/050\/01"},{"key":"38_CR24","doi-asserted-by":"publisher","first-page":"966","DOI":"10.1137\/S0097539788148959","volume":"23","author":"A. C.-C. Yao","year":"1994","unstructured":"A. C.-C. Yao. Near-optimal Time-Space Tradeoff for Element Distinctness. SIAM Journal on Computing, 23:966\u2013975, 1994.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44985-X_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T08:18:12Z","timestamp":1737533892000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44985-X_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540676904","9783540449850"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-44985-x_38","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}