{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T11:59:08Z","timestamp":1754481548375},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540646822"},{"type":"electronic","value":"9783540691068"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0054359","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T03:43:28Z","timestamp":1149651808000},"page":"107-118","source":"Crossref","is-referenced-by-count":22,"title":["Worst-case efficient external-memory priority queues"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jyrki","family":"Katajainen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"key":"10_CR1","first-page":"1259","volume":"3","author":"G. M. Adel'son-Vel'skii","year":"1962","unstructured":"G. M. Adel'son-Vel'skii and E. M. Landis. An algorithm for the organization of information. Soviet Mathematics, volume 3, pages 1259\u20131263, 1962.","journal-title":"Soviet Mathematics"},{"key":"10_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, volume 31, pages 1116\u20131127, 1988.","journal-title":"Communications of the ACM"},{"key":"10_CR3","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company, Reading, 1974."},{"key":"10_CR4","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1109\/TSE.1984.5010255","volume":"SE-10","author":"T.O. Alanko","year":"1984","unstructured":"T.O. Alanko, H.H. A. Erki\u00f6, and I. J. Haikala. Virtual memory behavior of some sorting algorithms. IEEE Transactions on Software Engineering, volume SE-10, pages 422\u2013431, 1984.","journal-title":"IEEE Transactions on Software Engineering"},{"key":"10_CR5","first-page":"334","volume-title":"Lecture Notes in Computer Science 955","author":"L. Arge","year":"1995","unstructured":"L. Arge. The buffer tree: A new technique for optimal I\/O-algorithms. In Proceedings of the 4th Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 955, Springer, Berlin\/Heidelberg, pages 334\u2013345, 1995."},{"key":"10_CR6","volume-title":"BRICS Dissertation DS-96-3","author":"L. Arge","year":"1996","unstructured":"L. Arge. Efficient external-memory data structures and applications. BRICS Dissertation DS-96-3, Department of Computer Science, University of Aarhus, \u00e5rhus, 1996."},{"key":"10_CR7","first-page":"540","volume-title":"On sorting strings in external memory","author":"L. Arge","year":"1997","unstructured":"L. Arge, P. Ferragina, R. Grossi, and J. S. Vitter. On sorting strings in external memory. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, ACM Press, New York, pages 540\u2013548, 1997."},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"R. Bayer and E. M. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, volume 1, pages 173\u2013189, 1972.","journal-title":"Acta Informatica"},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0207026","volume":"7","author":"M. R. Brown","year":"1978","unstructured":"M. R. Brown. Implementation and analysis of binomial queue algorithms. SIAM Journal on Computing, volume 7, pages 298\u2013319, 1978.","journal-title":"SIAM Journal on Computing"},{"key":"10_CR10","first-page":"1","volume-title":"Lecture Notes in Computer Science 318","author":"S. Carlsson","year":"1988","unstructured":"S. Carlsson, J.I. Munro, and P.V. Poblete. An implicit binomial queue with constant insertion time. In Proceedings of the 1st Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 318, Springer-Verlag, Berlin\/Heidelberg, pages 1\u201313, 1988."},{"key":"10_CR11","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 Computing Surveys, volume 11, pages 121\u2013137, 1979.","journal-title":"ACM Computing Surveys"},{"key":"10_CR12","volume-title":"Technical Report STAN-CS-72-259","author":"C. A. Crane","year":"1972","unstructured":"C. A. Crane. Linear lists and priority queues as balanced trees. Technical Report STAN-CS-72-259, Computer Science Department, Stanford University, Stanford, 1972."},{"key":"10_CR13","unstructured":"R. Fadel, K.V. Jakobsen, J. Katajainen, and J. Teuhola. Heaps and heapsort on secondary storage. To appear in Theoretical Computer Science."},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/174644.174645","volume":"41","author":"M. J. Fischer","year":"1994","unstructured":"M. J. Fischer and M. S. Paterson. Fishspear: A priority queue algorithm. Journal of the ACM, volume 41, pages 3\u201330, 1994.","journal-title":"Journal of the ACM"},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1145\/242223.242300","volume":"28","author":"G. A. Gibson","year":"1996","unstructured":"G. A. Gibson, J. S. Vitter, J. Wilkes et al. Strategic directions in storage I\/O issues in large-scale computing. ACM Computing Surveys, volume 28, pages 779\u2013793, 1996.","journal-title":"ACM Computing Surveys"},{"key":"10_CR16","first-page":"8","volume-title":"A dichromatic framework for balanced trees","author":"L. J. Guibas","year":"1978","unstructured":"L. J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science, IEEE, New York, pages 8\u201321, 1978."},{"issue":"number9","key":"10_CR17","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1145\/143371.143511","volume":"27","author":"K. Harty","year":"1992","unstructured":"K. Harty and D.R. Cheriton. Application-controlled physical memory using external page-cache management. In Proceedings of the 5th International Conference on Architectural Support for Programming Languages and Operating Systems, ACM SIGPLAN Notices, volume 27, number 9, pages 187\u2013197, 1992.","journal-title":"ACM SIGPLAN Notices"},{"key":"10_CR18","volume-title":"An Introduction to Parallel Algorithms","author":"J. J\u00e1J\u00e1","year":"1992","unstructured":"J. J\u00e1J\u00e1. An Introduction to Parallel Algorithms. Addison-Wesley Publishing Company, Reading, 1992."},{"key":"10_CR19","first-page":"240","volume-title":"Lecture Notes in Computer Science 824","author":"B.H.H. Juurlink","year":"1994","unstructured":"B.H.H. Juurlink and H. A. G. Wijshoff. The parallel hierarchical memory model. In Proceedings of the 4th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 824, Springer-Verlag, Berlin\/Heidelberg, pages 240\u2013251, 1994."},{"key":"10_CR20","volume-title":"volume 3\/ Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth. The Art of Computer Programming, volume 3\/ Sorting and Searching. Addison-Wesley Publishing Company, Reading, 1973."},{"issue":"number10","key":"10_CR21","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1145\/167962.165867","volume":"28","author":"K. Krueger","year":"1993","unstructured":"K. Krueger, D. Loftesness, A. Vahdat, and T. Anderson. Tools for the development of application-specific virtual memory management. In Proceedings of the 8th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, ACM SIGPLAN Notices, volume 28, number 10, pages 48\u201364, 1993.","journal-title":"ACM SIGPLAN Notices"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"A. LaMarca and R. E. Ladner. The influence of caches on the performance of heaps. The ACM Journal of Experimental Algorithmics, volume 1, article 4, 1996.","DOI":"10.1145\/235141.235145"},{"key":"10_CR23","volume-title":"Technical Report 90-09-05","author":"D. McNamee","year":"1990","unstructured":"D. McNamee and K. Amstrong. Extending the Mach external pager interface to accommodate user-level block replacement policies. Technical Report 90-09-05, Department of Computer Science and Engineering, University of Washington, Seattle, 1990."},{"key":"10_CR24","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1093\/comjnl\/34.5.428","volume":"34","author":"D. Naor","year":"1991","unstructured":"D. Naor, C. U. Martel, and N. S. Matloff. Performance of priority queue structures in a virtual memory environment. The Computer Journal, volume 34, pages 428\u2013437, 1991.","journal-title":"The Computer Journal"},{"key":"10_CR25","first-page":"29","volume-title":"Large-scale sorting in parallel memories","author":"M. H. Nodine","year":"1991","unstructured":"M. H. Nodine and J. S. Vitter. Large-scale sorting in parallel memories. In Proceedings of the 3rd ACM Symposium on Parallel Algorithms and Architectures, ACM Press, New York, pages 29\u201339, 1991."},{"issue":"number3","key":"10_CR26","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1109\/2.268880","volume":"27","author":"Y. N. Patt","year":"1994","unstructured":"Y. N. Patt. Guest editor's introduction: The I\/O subsystem \u2014 A candidate for improvement. IEEE Computer, volume 27, number 3, pages 15\u201316, 1994.","journal-title":"IEEE Computer"},{"key":"10_CR27","volume-title":"Computer Organization & Design: The Hardware\/Software Interface","author":"D. A. Patterson","year":"1994","unstructured":"D. A. Patterson and J. L. Hennessy. Computer Organization & Design: The Hardware\/Software Interface. Morgan Kaufmann Publishers, San Francisco, 1994."},{"key":"10_CR28","volume-title":"Algorithms","author":"R. Sedgewick","year":"1983","unstructured":"R. Sedgewick. Algorithms. Addison-Wesley Publishing Company, Reading, 1983."},{"key":"10_CR29","first-page":"59","volume-title":"On RAM priority queues","author":"M. Thorup","year":"1996","unstructured":"M. Thorup. On RAM priority queues. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York and SIAM, Philadelphia, pages 59\u201367, 1996."},{"key":"10_CR30","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, volume 12, pages 110\u2013147, 1994.","journal-title":"Algorithmica"},{"key":"10_CR31","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1145\/359460.359478","volume":"21","author":"J. Vuillemin","year":"1978","unstructured":"J. Vuillemin. A data structure for manipulating priority queues. Communications of the ACM, volume 21, pages 309\u2013315, 1978.","journal-title":"Communications of the ACM"},{"key":"10_CR32","doi-asserted-by":"publisher","first-page":"917","DOI":"10.1109\/32.29490","volume":"15","author":"L. M. Wegner","year":"1989","unstructured":"L. M. Wegner and J. I. Teuhola. The external heapsort. IEEE Transactions on Software Engineering, volume 15, pages 917\u2013925, 1989.","journal-title":"IEEE Transactions on Software Engineering"},{"key":"10_CR33","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J. W. J. Williams","year":"1964","unstructured":"J. W. J. Williams. Algorithm 232, Heapsort. Communications of the ACM, volume 7, pages 347\u2013348, 1964.","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054359","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T22:30:13Z","timestamp":1627425013000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0054359"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540646822","9783540691068"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/bfb0054359","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}