{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T03:43:28Z","timestamp":1743133408858,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540664277"},{"type":"electronic","value":"9783540483182"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"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":[[1999]]},"DOI":"10.1007\/3-540-48318-7_27","type":"book-chapter","created":{"date-parts":[[2007,10,25]],"date-time":"2007-10-25T20:20:56Z","timestamp":1193343656000},"page":"345-359","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["An Experimental Study of Priority Queues in External Memory"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Brengel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Crauser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo","family":"Ferragina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrich","family":"Meyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,27]]},"reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1145\/77600.77615","volume":"37","author":"R. Ahuja","year":"1990","unstructured":"R. Ahuja and K. Mehlhorn and J.B. Orlin and R.E. Tarjan, \u2018Faster Algorithms for the Shortest Path Problem\u2019, Journal of the ACM, 37:213\u2013223, 1990.","journal-title":"Journal of the ACM"},{"key":"27_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/3-540-60220-8_74","volume-title":"Workshop on Algorithms and Data Structures","author":"L. Arge","year":"1995","unstructured":"L. Arge, \u2018The Buffer Tree: A new technique for optimal I\/O-algorithms\u2019, Workshop on Algorithms and Data Structures, LNCS 955, 334\u2013345, 1995."},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"R. Bayer and E. McCreight, \u2018Organization and Maintenance of Large Ordered Indices\u2019, Acta Informatica, 1:173\u2013189, 1972.","journal-title":"Acta Informatica"},{"key":"27_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/BFb0054359","volume-title":"ScandinavianWorkshop on Algorithm Theory","author":"G. S. Brodal","year":"1998","unstructured":"G. S. Brodal and J. Katajainen, \u2018Worst-case efficient external memory priority queues\u2019, ScandinavianWorkshop on Algorithm Theory, LNCS 1432, 107\u2013117, 1998."},{"key":"27_CR5","unstructured":"Y. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter, \u2018External-memory graph algorithms\u2019, ACM-SIAM Symposium on Discrete Algorithms, 139\u2013149, 1995."},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"A. Crauser and K. Mehlhorn LEDA-SM, extending LEDA to Secondary Memory. Workshop on Algorithmic Engineering, 1999 (this volume).","DOI":"10.1007\/3-540-48318-7_19"},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"E.W. Dijkstra. \u2018A note on two problems in connection with graphs.\u2019 Num. Math., 1:269\u2013271, 1959.","journal-title":"Num. Math."},{"key":"27_CR8","unstructured":"M. Farach and P. Ferragina and S. Muthukrishnan. \u2018Overcoming the memory bottleneck in Suffix Tree construction\u2019, IEEE Symposium on Foundations of Computer Science, 194\u2013183, 1998."},{"key":"27_CR9","unstructured":"R. Fadel and K.V. Jakobsen and J. Katajainen and J. Teuhola, \u2018External heaps combined with effective buffering\u2019, Proc. Computing: The Australasian Theory Symposium, 1997."},{"key":"27_CR10","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"M.L. Fredman and R.E. Tarjan, \u2018Fibonacci heaps and their use in improved network optimization algorithms.\u2019, Journal of the ACM, 34:596\u2013615, 1987.","journal-title":"Journal of the ACM"},{"key":"27_CR11","unstructured":"D. Hutchinson, A. Maheshwari, J. Sack and R. Velicescu, \u2018Early experiences in implementing buffer trees\u2019, Workshop on Algorithmic Engineering, 92\u2013103, 1997."},{"key":"27_CR12","unstructured":"\u2018IEEE standard 754-1985 for binary floating-point arithmetic\u2019, reprinted in SIGPLAN 22, 1987."},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"V. Kumar and E.J. Schwabe, \u2018Improved Algorithms and Data Structures for Solving Graph Problems in External Memory\u2019, IEEE Symposium on Parallel and Distributed Processing, 169\u2013177, 1996.","DOI":"10.1109\/SPDP.1996.570330"},{"key":"27_CR14","doi-asserted-by":"crossref","unstructured":"A. LaMarca and R.E. Ladner, \u2018The influence of caches on the performances of heaps\u2019, Tech. Report 96-02-03, UW University, 1996. To appear in Journal of Experimental Algorithmics.","DOI":"10.1145\/235141.235145"},{"key":"27_CR15","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1145\/204865.204889","volume":"38","author":"K. Mehlhorn","year":"1995","unstructured":"K. Mehlhorn and S. N\u00e4her. LEDA: A platform for combinatorial and geometric computing. Communication of the ACM, 38:96\u2013102, 1995.","journal-title":"Communication of the ACM"},{"issue":"5","key":"27_CR16","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, \u2018Performance of Priority Queue Structures in a Virtual Memory Environment\u2019, The Computer Journal, 34(5):428\u2013437, 1991.","journal-title":"The Computer Journal"},{"issue":"3","key":"27_CR17","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1109\/2.268881","volume":"27","author":"C. Ruemmler","year":"1994","unstructured":"C. Ruemmler and J. Wilkes, \u2018An introduction to disk drive modeling\u2019, IEEE Computer, 27(3):17\u201329, 1994.","journal-title":"IEEE Computer"},{"key":"27_CR18","series-title":"Lect Notes Comput Sci","volume-title":"Workshop on Algorithmic Engineering and Experimentation","author":"P. Sanders","year":"1999","unstructured":"P. Sanders. \u2018Fast priority queues for cached memory\u2019, ALENEX\u2019 99. Workshop on Algorithmic Engineering and Experimentation, LNCS, 1999 (to appear)."},{"key":"27_CR19","unstructured":"M. Thorup. \u2018On RAM priority queues\u2019, ACM-SIAM Symposium on Discrete Algorithms, 59\u201367, 1996."},{"key":"27_CR20","doi-asserted-by":"crossref","unstructured":"D.E. Vengroff and J.S. Vitter. \u2018Supporting I\/O-efficient scientific computation using TPIE\u2019, IEEE Symposium on Parallel and Distributed Processing, 74\u201377, 1995.","DOI":"10.1109\/SPDP.1995.530667"},{"issue":"2-3","key":"27_CR21","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, \u2018Optimal Algorithms for Parallel Memory I:Two-Level Memories\u2019, Algorithmica,12(2-3):110\u2013147, 1994.","journal-title":"Algorithmica"},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"J. Vitter. External memory algorithms. Invited Tutorial, ACM Symposium on Principles of Database Systems, 1998. Also Invited Paper in European Symposium on Algorithms, 1998.","DOI":"10.1145\/275487.275501"},{"key":"27_CR23","unstructured":"J.W.J. William. Algorithm 232 (heapsort), In Communications of the ACM, 347\u2013348,1964."}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48318-7_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T22:29:06Z","timestamp":1737498546000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48318-7_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540664277","9783540483182"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-48318-7_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"27 July 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}