{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T11:08:18Z","timestamp":1742987298106,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":71,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662242"},{"type":"electronic","value":"9783540485230"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/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-48523-6_10","type":"book-chapter","created":{"date-parts":[[2007,12,10]],"date-time":"2007-12-10T12:06:31Z","timestamp":1197288391000},"page":"119-133","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Online Data Structures in External Memory"],"prefix":"10.1007","author":[{"given":"Jeffrey Scott","family":"Vitter","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,1,18]]},"reference":[{"key":"10_CR1","unstructured":"P.K. Agarwal, L. Arge, G.S. Brodal, and J.S. Vitter. I\/O-efficient dynamic point location in monotone planar subdivisions. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 11\u201320, 1999."},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"P.K. Agarwal, L. Arge, J. Erickson, P.G. Franciosa, and J.S. Vitter. Efficient searching with linear constraints. In Proc. 17th ACM Symposium on Principles of Database Systems, 169\u2013178, 1998.","DOI":"10.1145\/275487.275506"},{"key":"10_CR3","unstructured":"P.K. Agarwal, L. Arge, T.M. Murali, K. Varadarajan, and J.S. Vitter. I\/O-efficient algorithms for contour line extraction and planar graph blocking. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 117\u2013126, 1998."},{"key":"10_CR4","first-page":"1","volume-title":"Advances in Discrete and Computational Geometry","author":"P.K. Agarwal","year":"1999","unstructured":"P.K. Agarwal and J. Erickson. Geometric range searching and its relatives. In B. Chazelle, J.E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry, volume 23 of Contemporary Mathematics, 1\u201356. AMS Press, Providence, RI, 1999."},{"key":"10_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/3-540-60220-8_74","volume-title":"Proceedings of the 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 Proceedings of the Workshop on Algorithms and Data Structures, volume 955 of Lecture Notes in Computer Science, 334\u2013345. Springer-Verlag, 1995. A complete version appears as BRICS technical report RS-96-28, University of Aarhus."},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"L. Arge, K.H. Hinrichs, J. Vahrenhold, and J.S. Vitter. Efficient bulk operations on dynamic R-trees. In Proceedings of the 1st Workshop on Algorithm Engineering and Experimentation, Baltimore, January 1999.","DOI":"10.1007\/3-540-48518-X_20"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"L. Arge, V. Samoladas, and J.S. Vitter. Two-dimensional indexability and optimal range search indexing. In Proceedings of the ACM Symposium Principles of Database Systems, Philadelphia, PA, May-June 1999.","DOI":"10.1145\/303976.304010"},{"key":"10_CR8","unstructured":"L. Arge and J.S. Vitter. Optimal dynamic interval management in external memory. In Proceedings of the IEEE Symposium on Foundations of Computer Science, 560\u2013569, Burlington, VT, October 1996."},{"issue":"5","key":"10_CR9","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/BF00289146","volume":"26","author":"R.A. Baeza-Yates","year":"1989","unstructured":"R.A. Baeza-Yates. Expected behaviour of B+-trees under random insertions. Acta Informatica, 26(5), 439\u2013472, 1989.","journal-title":"Acta Informatica"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"R.D. Barve, E.A.M. Shriver, P.B. Gibbons, B.K. Hillyer, Y. Matias, and J.S. Vitter. Modeling and optimizing I\/O throughput of multiple disks on a bus: the long version. Technical report, Bell Labs, 1997.","DOI":"10.1145\/277851.277936"},{"key":"10_CR11","unstructured":"R.D. Barve and J.S. Vitter. External memory algorithms with dynamically changing memory allocations: Long version. Technical Report CS-1998-09, Duke University, 1998."},{"key":"10_CR12","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."},{"issue":"4","key":"10_CR13","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/s007780050028","volume":"5","author":"B. Becker","year":"1996","unstructured":"B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer. An asymptotically optimal multiversion B-tree. The VLDB Journal, 5(4), 264\u2013275, December 1996.","journal-title":"The VLDB Journal"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An efficient and robust access method for points and rectangles. In Proceedings of the SIGMOD International Conference on Management of Data, 322\u2013331, 1990.","DOI":"10.1145\/93605.98741"},{"issue":"6","key":"10_CR15","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1145\/358841.358850","volume":"23","author":"J.L. Bentley","year":"1980","unstructured":"J.L. Bentley. Multidimensional divide and conquer. Communications of the ACM, 23(6), 214\u2013229, 1980.","journal-title":"Communications of the ACM"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"S. Berchtold, C. B\u00f6hm, and H.-P. Kriegel. Improving the query performance of high-dimensional index structures by bulk load operations. In Proceedings of the International Conference on Extending Database Technology, 1998.","DOI":"10.1007\/BFb0100987"},{"key":"10_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/BFb0054359","volume-title":"Proceedings of the Scandinavian Workshop on Algorithms Theory","author":"G.S. Brodal","year":"1998","unstructured":"G.S. Brodal and J. Katajainen. Worst-case efficient external-memory priority queues. In Proceedings of the Scandinavian Workshop on Algorithms Theory, volume 1432of Lecture Notes in Computer Science, 107\u2013118, Stockholm, Sweden, July 1998. Springer-Verlag."},{"key":"10_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/3-540-60220-8_78","volume-title":"Proceedings of the Workshop on Algorithms and Data Structures","author":"P. Callahan","year":"1995","unstructured":"P. Callahan, M.T. Goodrich, and K. Ramaiyer. Topology B-trees and their applications. In Proceedings of the Workshop on Algorithms and Data Structures, volume 955 of Lecture Notes in Computer Science, 381\u2013392. Springer-Verlag, 1995."},{"key":"10_CR19","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle. Filtering search: a new approach to query-answering. SIAM Journal on Computing, 15, 703\u2013724, 1986.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"10_CR20","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1145\/77600.77614","volume":"37","author":"B. Chazelle","year":"1990","unstructured":"B. Chazelle. Lower bounds for orthogonal range searching: I. The reporting case. Journal of the ACM, 37(2), 200\u2013212, April 1990.","journal-title":"Journal of the ACM"},{"key":"10_CR21","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF02187875","volume":"2","author":"B. Chazelle","year":"1987","unstructured":"B. Chazelle and H. Edelsbrunner. Linear space data structures for two types of range search. Discrete & Computational Geometry, 2, 113\u2013126, 1987.","journal-title":"Discrete & Computational Geometry"},{"issue":"2","key":"10_CR22","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1145\/176979.176981","volume":"26","author":"P.M. Chen","year":"1994","unstructured":"P.M. Chen, E.K. Lee, G.A. Gibson, R.H. Katz, and D.A. Patterson. RAID: high-performance, reliable secondary storage. ACM Computing Surveys, 26(2), 145\u2013185, June 1994.","journal-title":"ACM Computing Surveys"},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"Y.-J. Chiang and C.T. Silva. External memory techniques for isosurface extraction in scientific visualization. In J. Abello and J.S. Vitter, editors, External Memory Algorithms and Visualization, Providence, RI, 1999. AMS Press.","DOI":"10.1090\/dimacs\/050\/14"},{"issue":"2","key":"10_CR24","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. Comput. Surveys, 11(2), 121\u2013137, 1979.","journal-title":"Comput. Surveys"},{"key":"10_CR25","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1080\/00207168308803364","volume":"13","author":"H. Edelsbrunner","year":"1983","unstructured":"H. Edelsbrunner. A new approach to rectangle intersections, part I. Int. J.Computer Mathematics, 13, 209\u2013219, 1983.","journal-title":"Int. J.Computer Mathematics"},{"key":"10_CR26","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1080\/00207168308803365","volume":"13","author":"H. Edelsbrunner","year":"1983","unstructured":"H. Edelsbrunner. A new approach to rectangle intersections, part II. Int. J. Computer Mathematics, 13, 221\u2013229, 1983.","journal-title":"Int. J. Computer Mathematics"},{"issue":"2","key":"10_CR27","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1145\/46157.330532","volume":"20","author":"R.J. Enbody","year":"1988","unstructured":"R.J. Enbody and H.C. Du. Dynamic hashing schemes. ACM Computing Surveys, 20(2), 85\u2013113, June 1988.","journal-title":"ACM Computing Surveys"},{"key":"10_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s007780050030","volume":"6","author":"G. Evangelidis","year":"1997","unstructured":"G. Evangelidis, D.B. Lomet, and B. Salzberg. The hBII-tree: A multi-attribute index supporting concurrency, recovery and node consolidation. VLDB Journal, 6, 1\u201325, 1997.","journal-title":"VLDB Journal"},{"issue":"3","key":"10_CR29","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1145\/320083.320092","volume":"4","author":"R. Fagin","year":"1979","unstructured":"R. Fagin, J. Nievergelt, N. Pippinger, and H.R. Strong. Extendible hashing\u2014a fast access method for dynamic files. ACM Transactions on Database Systems, 4(3), 315\u2013344, 1979.","journal-title":"ACM Transactions on Database Systems"},{"issue":"4","key":"10_CR30","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF00264279","volume":"20","author":"P. Flajolet","year":"1983","unstructured":"P. Flajolet. On the performance evaluation of extendible hashing and trie searching. Acta Informatica, 20(4), 345\u2013369, 1983.","journal-title":"Acta Informatica"},{"key":"10_CR31","unstructured":"W. Frakes and R. Baeza-Yates, editors. Information Retrieval: Data Structures and Algorithms. Prentice-Hall, 1992."},{"issue":"2","key":"10_CR32","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1145\/280277.280279","volume":"30","author":"V. Gaede","year":"1998","unstructured":"V. Gaede and O. G\u00fcnther. Multidimensional access methods. Computing Surveys, 30(2), 170\u2013231, June 1998.","journal-title":"Computing Surveys"},{"issue":"4","key":"10_CR33","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, and J. Wilkes. Report of the working group on storage I\/O issues in large-scale computing. ACM Computing Surveys, 28(4), 779\u2013793, December 1996.","journal-title":"ACM Computing Surveys"},{"key":"10_CR34","unstructured":"D. Greene. An implementation and performance analysis of spatial data access methods. In Proceedings of the IEEE International Conference on Data Engineering, 606\u2013615, 1989."},{"key":"10_CR35","volume-title":"External Memory Algorithms and Visualization","author":"R. Grossi","year":"1999","unstructured":"R. Grossi and G.F. Italiano. Efficient cross-trees for external memory. In J. Abello and J.S. Vitter, editors, External Memory Algorithms and Visualization. AMS Press, Providence, RI, 1999."},{"key":"10_CR36","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1007\/3-540-63165-8_215","volume-title":"Information and Computation","author":"R. Grossi","year":"1997","unstructured":"R. Grossi and G.F. Italiano. Efficient splitting and merging algorithms for order decomposable problems. Information and Computation, in press. An earlier version appears in Proceedings of the 24th International Colloquium on Automata, Languages and Programming, volume 1256 of Lecture Notes in Computer Science, Springer Verlag, 605\u2013615, 1997."},{"key":"10_CR37","doi-asserted-by":"crossref","unstructured":"A. Guttman. R-trees: A dynamic index structure for spatial searching. In Proceedings of the ACM SIGMOD Conference on Management of Data, 47\u201357, 1985.","DOI":"10.1145\/971697.602266"},{"key":"10_CR38","doi-asserted-by":"crossref","unstructured":"J.M. Hellerstein, E. Koutsoupias, and C.H. Papadimitriou. On the analysis of indexing schemes. In Proceedings of the 16th ACM Symposium on Principles of Database Systems, 249\u2013256, Tucson, AZ, May 1997.","DOI":"10.1145\/263661.263688"},{"issue":"2-3","key":"10_CR39","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/BF01185210","volume":"12","author":"L. Hellerstein","year":"1994","unstructured":"L. Hellerstein, G. Gibson, R.M. Karp, R.H. Katz, and D.A. Patterson. Coding techniques for handling failures in large disk arrays. Algorithmica, 12(2-3), 182\u2013208, 1994.","journal-title":"Algorithmica"},{"key":"10_CR40","unstructured":"K.H. Hinrichs. The grid file system: Implementation and case studies of applications. PhD thesis, Dept. Information Science, ETH, Z\u00fcrich, 1985."},{"key":"10_CR41","doi-asserted-by":"crossref","unstructured":"I. Kamel and C. Faloutsos. On packing R-trees. In Proceedings of the 2nd International Conference on Information and Knowledge Management, 490\u2013499, 1993.","DOI":"10.1145\/170088.170403"},{"key":"10_CR42","unstructured":"I. Kamel and C. Faloutsos. Hilbert R-tree: An improved R-tree using fractals. In Proceedings of the 20th International Conference on Very Large Databases, 500\u2013509, 1994."},{"key":"10_CR43","first-page":"31","volume":"3B","author":"I. Kamel","year":"1996","unstructured":"I. Kamel, M. Khalil, and V. Kouramajian. Bulk insertion in dynamic R-trees. In Proceedings of the 4th International Symposium on Spatial Data Handling, 3B, 31\u201342, 1996.","journal-title":"Proceedings of the 4th International Symposium on Spatial Data Handling"},{"issue":"3","key":"10_CR44","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1006\/jcss.1996.0043","volume":"52","author":"P.C. Kanellakis","year":"1996","unstructured":"P.C. Kanellakis, S. Ramaswamy, D.E. Vengroff, and J.S. Vitter. Indexing for data models with constraints and classes. Journal of Computer and System Science, 52(3), 589\u2013612, 1996.","journal-title":"Journal of Computer and System Science"},{"key":"10_CR45","unstructured":"K.V.R. Kanth and A.K. Singh. Optimal dynamic range searching in non-replicating index structures. In Proceedings of the 7th International Conference on Database Theory, Jerusalem, January 1999."},{"key":"10_CR46","volume-title":"The Art of Computer Programming","author":"D.E. Knuth","year":"1998","unstructured":"D.E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, Reading MA, second edition, 1998.","edition":"second edition"},{"key":"10_CR47","doi-asserted-by":"crossref","unstructured":"E. Koutsoupias and D.S. Taylor. Tight bounds for 2-dimensional indexing schemes. In Proceedings of the 17th ACM Symposium on Principles of Database Systems, Seattle, WA, June 1998.","DOI":"10.1145\/275487.275494"},{"key":"10_CR48","unstructured":"R. Krishnamurthy and K.-Y. Wang. Multilevel grid files. Tech. Report, IBM T. J. Watson Center, Yorktown Heights, NY, November 1985."},{"key":"10_CR49","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/BF00263927","volume":"19","author":"K. K\u00fcspert","year":"1983","unstructured":"K. K\u00fcspert. Storage utilization in B*-trees with a generalized overflow technique. Acta Informatica, 19, 35\u201355, 1983.","journal-title":"Acta Informatica"},{"key":"10_CR50","unstructured":"W. Litwin. Linear hashing: A new tool for files and tables addressing. In International Conference On Very Large Data Bases, 212\u2013223, Montreal, Quebec, Canada, October 1980."},{"issue":"4","key":"10_CR51","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1145\/99935.99949","volume":"15","author":"D.B. Lomet","year":"1990","unstructured":"D.B. Lomet and B. Salzberg. The hB-tree: a multiattribute indexing method with good guaranteed performance. ACM Transactions on Database Systems, 15(4), 625\u2013658, 1990.","journal-title":"ACM Transactions on Database Systems"},{"issue":"3","key":"10_CR52","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s007780050042","volume":"6","author":"D.B. Lomet","year":"1997","unstructured":"D.B. Lomet and B. Salzberg. Concurrency and recovery for index trees. The VLDB Journal, 6(3), 224\u2013240, 1997.","journal-title":"The VLDB Journal"},{"issue":"2","key":"10_CR53","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"E.M. McCreight","year":"1985","unstructured":"E.M. McCreight. Priority search trees. SIAM Journal on Computing, 14(2), 257\u2013276, May 1985.","journal-title":"SIAM Journal on Computing"},{"key":"10_CR54","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1109\/TSE.1982.236022","volume":"SE-8","author":"H. Mendelson","year":"1982","unstructured":"H. Mendelson. Analysis of extendible hashing. IEEE Transactions on Software Engineering, SE-8, 611\u2013619, November 1982.","journal-title":"IEEE Transactions on Software Engineering"},{"key":"10_CR55","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/348.318586","volume":"9","author":"J. Nievergelt","year":"1984","unstructured":"J. Nievergelt, H. Hinterberger, and K.C. Sevcik. The grid file: An adaptable, symmetric multi-key file structure. ACM Trans. Database Syst., 9, 38\u201371, 1984.","journal-title":"ACM Trans. Database Syst."},{"key":"10_CR56","series-title":"Lect Notes Comput Sci","volume-title":"Algorithmic Foundations of GIS","author":"J. Nievergelt","year":"1997","unstructured":"J. Nievergelt and P. Widmayer. Spatial data structures: Concepts and design choices. In M. van Kreveld, J. Nievergelt, T. Roos, and P. Widmayer, editors, Algorithmic Foundations of GIS, volume 1340 of Lecture Notes in Computer Science. Springer-Verlag, 1997."},{"key":"10_CR57","unstructured":"S. Ramaswamy and S. Subramanian. Path caching: a technique for optimal external searching. Proceedings of the 13th ACM Conference on Principles of Database Systems, 1994."},{"key":"10_CR58","doi-asserted-by":"crossref","unstructured":"J.T. Robinson. The k-d-b-tree: a search structure for large multidimensional dynamic indexes. In Proc. ACM Conference Principles Database Systems, 10\u201318, 1981.","DOI":"10.1145\/582318.582321"},{"key":"10_CR59","doi-asserted-by":"crossref","unstructured":"C. Ruemmler and J. Wilkes. An introduction to disk drive modeling. IEEE Computer, 17\u201328, March 1994.","DOI":"10.1109\/2.268881"},{"key":"10_CR60","doi-asserted-by":"crossref","unstructured":"V. Samoladas and D. Miranker. A lower bound theorem for indexing schemes and its application to multidimensional range queries. In Proc. 17th ACM Conf. on Princ. of Database Systems, Seattle, WA, June 1998.","DOI":"10.1145\/275487.275493"},{"key":"10_CR61","unstructured":"B. Seeger and H.-P. Kriegel. The buddy-tree: An efficient and robust access method for spatial data base systems. In Proc. 16th VLDB Conference, 590\u2013601, 1990."},{"key":"10_CR62","doi-asserted-by":"crossref","unstructured":"E. Shriver, A. Merchant, and J. Wilkes. An analytic behavior model for disk drives with readahead caches and request reordering. In Joint International Conference on Measurement and Modeling of Computer Systems, June 1998.","DOI":"10.1145\/277851.277906"},{"key":"10_CR63","unstructured":"S. Subramanian and S. Ramaswamy. The P-range tree: a new data structure for range searching in secondary memory. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 1995."},{"key":"10_CR64","unstructured":"J. van den Bercken, B. Seeger, and P. Widmayer. A generic approach to bulk loading multidimensional index structures. In Proceedings 23rd VLDB Conference, 406\u2013415, 1997."},{"issue":"3","key":"10_CR65","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1109\/69.599929","volume":"9","author":"P.J. Varman","year":"1997","unstructured":"P.J. Varman and R.M. Verma. An efficient multiversion access structure. IEEE Transactions on Knowledge and Data Engineering, 9(3), 391\u2013409, May\/June 1997.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"10_CR66","doi-asserted-by":"crossref","unstructured":"D.E. Vengroff and J.S. Vitter. Efficient 3-d range searching in external memory. In Proceedings of the ACM Symposium on Theory of Computation, 192\u2013201, Philadelphia, PA, May 1996.","DOI":"10.1145\/237814.237864"},{"key":"10_CR67","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of the 1991 Symposium on Theoretical Aspects of Computer Science","author":"J.S. Vitter","year":"1991","unstructured":"J.S. Vitter. Efficient memory access in large-scale computation. In Proceedings of the 1991 Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science. Springer-Verlag, 1991. Invited paper."},{"key":"10_CR68","volume-title":"External Memory Algorithms and Visualization","author":"J.S. Vitter","year":"1999","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, Providence, RI, 1999. An updated version is available via the author\u2019s web page http:\/\/www.cs.duke.edu\/~jsv\/."},{"issue":"2-3","key":"10_CR69","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-3), 110\u2013147, 1994.","journal-title":"Algorithmica"},{"issue":"3","key":"10_CR70","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1145\/3828.3839","volume":"32","author":"D. Willard","year":"1985","unstructured":"D. Willard and G. Lueker. Adding range restriction capability to dynamic data structures. Journal of the ACM, 32(3), 597\u2013617, 1985.","journal-title":"Journal of the ACM"},{"key":"10_CR71","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/BF00289075","volume":"9","author":"A.C. Yao","year":"1978","unstructured":"A.C. Yao. On random 2-3 trees. Acta Informatica, 9, 159\u2013170, 1978.","journal-title":"Acta Informatica"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48523-6_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T03:03:50Z","timestamp":1642820630000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-48523-6_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662242","9783540485230"],"references-count":71,"URL":"https:\/\/doi.org\/10.1007\/3-540-48523-6_10","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":"18 January 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}