{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T18:55:18Z","timestamp":1775242518801,"version":"3.50.1"},"reference-count":365,"publisher":"Emerald","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,6,9]]},"abstract":"Data sets in large applications are often too massive to fit completely inside the computer's internal memory. The resulting input\/output communication (or I\/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottleneck. In this manuscript, we survey the state of the art in the design and analysis of algorithms and data structures for external memory (or EM for short), where the goal is to exploit locality and parallelism in order to reduce the I\/O costs. We consider a variety of EM paradigms for solving batched and online problems efficiently in external memory.<\/jats:p>\n For the batched problem of sorting and related problems like permuting and fast Fourier transform, the key paradigms include distribution and merging. The paradigm of disk striping offers an elegant way to use multiple disks in parallel. For sorting, however, disk striping can be nonoptimal with respect to I\/O, so to gain further improvements we discuss distribution and merging techniques for using the disks independently. We also consider useful techniques for batched EM problems involving matrices, geometric data, and graphs.<\/jats:p>\n In the online domain, canonical EM applications include dictionary lookup and range searching. The two important classes of indexed data structures are based upon extendible hashing and B-trees. The paradigms of filtering and bootstrapping provide convenient means in online data structures to make effective use of the data accessed from disk. We also re-examine some of the above EM problems in slightly different settings, such as when the data items are moving, when the data items are variable-length such as character strings, when the data structure is compressed to save space, or when the allocated amount of internal memory can change dynamically.<\/jats:p>\n Programming tools and environments are available for simplifying the EM programming task. We report on some experiments in the domain of spatial databases using the TPIE system (Transparent Parallel I\/O programming Environment). The newly developed EM algorithms and data structures that incorporate the paradigms we discuss are significantly faster than other methods used in practice.<\/jats:p>","DOI":"10.1561\/0400000014","type":"journal-article","created":{"date-parts":[[2008,6,29]],"date-time":"2008-06-29T16:20:24Z","timestamp":1214756424000},"page":"305-474","source":"Crossref","is-referenced-by-count":113,"title":["Algorithms and Data Structures for External Memory"],"prefix":"10.1561","volume":"2","author":[{"given":"Jeffrey Scott","family":"Vitter","sequence":"first","affiliation":[{"name":"Purdue University Department of Computer Science, , West Lafayette, Indiana, 47907\u20132107,","place":["USA"]}]}],"member":"140","published-online":{"date-parts":[[2008,6,9]]},"reference":[{"key":"2026040314023131800_ref001","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0734-189X(84)90079-3","article-title":"A B+-tree structure for large quadtrees","volume":"27","author":"Abel","year":"1984","journal-title":"Computer Vision, Graphics, and Image Processing"},{"issue":"3","key":"2026040314023131800_ref002","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1007\/s00453-001-0088-5","article-title":"A functional approach to external graph algorithms","volume":"32","author":"Abello","year":"2002","journal-title":"Algorithmica"},{"key":"2026040314023131800_ref003","author":"Abello","journal-title":"Handbook of Massive Data Sets"},{"key":"2026040314023131800_ref004","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1145\/291006.291026","article-title":"Active disks: Programming model, algorithms and evaluation","volume":"33","author":"Acharya","year":"1998","journal-title":"ACM SIGPLAN Notices"},{"key":"2026040314023131800_ref005","first-page":"173","article-title":"New coding techniques for improved bandwidth utilization","author":"Adler","year":"1996","journal-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science"},{"key":"2026040314023131800_ref006","first-page":"11","article-title":"I\/O-efficient dynamic point location in monotone planar subdivisions","author":"Agarwal","year":"1999","journal-title":"Proceedings of the ACM- SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref007","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-35589-8_48","article-title":"From LIDAR to GRID DEM: A scalable approach","author":"Agarwal","year":"2006","journal-title":"Proceedings of the International Symposium on Spatial Data Handling"},{"issue":"1","key":"2026040314023131800_ref008","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/S0022-0000(02)00035-1","article-title":"Indexing moving points","volume":"66","author":"Agarwal","year":"2003","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314023131800_ref009","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1006\/jcss.2000.1709","article-title":"Efficient searching with linear constraints","volume":"61","author":"Agarwal","year":"2000","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314023131800_ref010","first-page":"117126","article-title":"I\/O- efficient algorithms for contour line extraction and planar graph blocking","author":"Agarwal","year":"1998","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref011","first-page":"115","article-title":"A framework for index bulk loading and dynamization","author":"Agarwal","year":"2001","journal-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming"},{"key":"2026040314023131800_ref012","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/3-540-44634-6_6","article-title":"Time responsive external data structures for moving points","author":"Agarwal","year":"2001","journal-title":"Proceedings of the Workshop on Algorithms and Data Structures"},{"key":"2026040314023131800_ref013","first-page":"7","article-title":"I\/O-efficient structures for orthogonal range-max and stabbing-max queries","author":"Agarwal","year":"2003","journal-title":"Proceedings of the European Symposium on Algorithms"},{"key":"2026040314023131800_ref014","first-page":"355","article-title":"I\/O-efficient construction of constrained delaunay triangulations","author":"Agarwal","year":"2005","journal-title":"Proceedings of the European Symposium on Algo-rithms"},{"key":"2026040314023131800_ref015","first-page":"803","article-title":"An optimal dynamic interval stabbingmax data structure?","author":"Agarwal","year":"2005","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref016","article-title":"I\/O-efficient batched union-find and its applications to terrain analysis","author":"Agarwal","year":"2006","journal-title":"Proceedings of the ACM Symposium on Computational Geometry"},{"issue":"3","key":"2026040314023131800_ref017","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/s00454-002-2817-1","article-title":"Box-trees and R-trees with near-optimal query time","volume":"28","author":"Agarwal","year":"2002","journal-title":"Discrete and Computational Geometry"},{"key":"2026040314023131800_ref018","first-page":"1","article-title":"Geometric range searching and its relatives","author":"Agarwal","year":"1999","journal-title":"Advances in Discrete and Computational Geometry"},{"key":"2026040314023131800_ref019","first-page":"148","article-title":"Maintaining the approximate extent measures of moving points","author":"Agarwal","year":"2001","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref020","first-page":"305","article-title":"A model for hierarchical memory","author":"Aggarwal","year":"1987","journal-title":"Proceedings of the ACM Symposium on Theory of Computing"},{"key":"2026040314023131800_ref021","first-page":"204","article-title":"Hierarchical memory with block transfer","author":"Aggarwal","year":"1987","journal-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science"},{"key":"2026040314023131800_ref022","first-page":"659","article-title":"Optimal parallel sorting in multi-level stor-age","author":"Aggarwal","year":"1994","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"issue":"9","key":"2026040314023131800_ref023","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","article-title":"The Input\/Output complexity of sorting and related problems","volume":"31","author":"Aggarwal","year":"1988","journal-title":"Communications of the ACM"},{"key":"2026040314023131800_ref024","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-47534-9","author":"Aggarwal","year":"2007","journal-title":"Data Streams: Models and Algorithms"},{"issue":"3","key":"2026040314023131800_ref025","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/S0019-9958(84)80015-7","article-title":"Hash functions for priority queues","volume":"63","author":"Ajtai","year":"1984","journal-title":"Information and Control"},{"key":"2026040314023131800_ref026","first-page":"208","article-title":"Characterizing the performance of flash memory storage devices and its impact on algorithm design","author":"Ajwani","year":"2008","journal-title":"Proceedings of the International Workshop on Experimental Algorithmics"},{"key":"2026040314023131800_ref027","first-page":"3","article-title":"Improved external memory BFS imple-mentation","author":"Ajwani","year":"2007","journal-title":"Proceedings of the Workshop on Algorithm Engineering and Experiments"},{"issue":"1","key":"2026040314023131800_ref028","doi-asserted-by":"crossref","DOI":"10.1016\/j.ic.2005.01.003","article-title":"Integrated prefetchingand caching in single and parallel disk systems","volume":"198","author":"Albers","journal-title":"Information and Computation"},{"issue":"12-2","key":"2026040314023131800_ref029","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/BF01185206","article-title":"The uniform memory hierarchy model of computation","volume":"12","author":"Alpern","year":"1994","journal-title":"Algorithmica"},{"key":"2026040314023131800_ref030","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/BFb0015411","article-title":"The I\/O-complexity of ordered binary-decision diagram manipu-lation","author":"Arge","year":"1995","journal-title":"Proceedings of the International Symposium on Algorithms and Computation"},{"key":"2026040314023131800_ref031","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-0005-6_9","article-title":"External memory data structures","author":"Arge","year":"2002","journal-title":"Handbook of Massive Data Sets"},{"issue":"1","key":"2026040314023131800_ref032","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-003-1021-x","article-title":"The buffer tree: A technique for designing batched external data structures","volume":"37","author":"Arge","year":"2003","journal-title":"Algorithmica"},{"key":"2026040314023131800_ref033","article-title":"Cache-oblivious data structures","author":"Arge","journal-title":"Handbook on Data Structures and Applications"},{"issue":"2","key":"2026040314023131800_ref034","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/j.jalgor.2004.04.001","article-title":"On external-memory MST, SSSP, and multi-way planar graph separation","volume":"53","author":"Arge","year":"2004","journal-title":"Journal of Algorithms"},{"key":"2026040314023131800_ref035","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1023\/A:1025526421410","article-title":"Efficient flow computation on massive grid datasets","volume":"7","author":"Arge","year":"2003","journal-title":"GeoInfor- matica"},{"key":"2026040314023131800_ref036","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-35589-8_51","article-title":"I\/O-efficient hierarchical watershed decomposition of grid terrains models","author":"Arge","year":"2006","journal-title":"Proceedings of the International Symposium on Spatial Data Handling"},{"key":"2026040314023131800_ref037","article-title":"I\/O-efficient point location using persistent B-trees","author":"Arge","year":"2003","journal-title":"Workshop on Algorithm Engineering and Experimentation"},{"key":"2026040314023131800_ref038","first-page":"347","article-title":"The priority R-tree: A practically efficient and worst-case optimal R-tree","author":"Arge","year":"2004","journal-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data"},{"key":"2026040314023131800_ref039","first-page":"540","article-title":"On sorting strings in external memory","author":"Arge","year":"1997","journal-title":"Proceedings of the ACM Symposium on Theory of Computing"},{"key":"2026040314023131800_ref040","doi-asserted-by":"crossref","DOI":"10.1145\/1378533.1378573","article-title":"Fundamental parallel algorithms for private-cache chip multiprocessors","author":"Arge","year":"2008","journal-title":"Proceedings of the ACM Symposium on Parallel Algorithms and Architectures"},{"key":"2026040314023131800_ref041","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1007\/s00453-001-0107-6","article-title":"Efficient bulk operations on dynamic R-trees","volume":"33","author":"Arge","year":"2002","journal-title":"Algorithmica"},{"key":"2026040314023131800_ref042","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/3-540-57155-8_238","article-title":"A general lower bound on the I\/O- complexity of comparison-based algorithms","author":"Arge","year":"1993","journal-title":"Proceedings of the Workshop on Algorithms and Data Structures"},{"key":"2026040314023131800_ref043","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1007\/978-3-540-27836-8_15","article-title":"External memory algorithms for diameter and all-pairs shortest-paths on sparse graphs","author":"Arge","year":"2004","journal-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming"},{"issue":"2","key":"2026040314023131800_ref044","doi-asserted-by":"crossref","first-page":"105","DOI":"10.7155\/jgaa.00063","article-title":"On external-memory planar depth first search","volume":"7","author":"Arge","year":"2003","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"2026040314023131800_ref045","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1090\/dimacs\/050\/08","article-title":"On showing lower bounds for external-memory computational geometry problems","author":"Arge","year":"1999","journal-title":"External Memory Algorithms and Visualization"},{"key":"2026040314023131800_ref046","article-title":"A unified approach for indexed and non-indexed spatial joins","author":"Arge","year":"2000","journal-title":"Proceedings of the International Conference on Extending Database Technology"},{"key":"2026040314023131800_ref047","first-page":"570","article-title":"Scalable sweeping-based spatial join","author":"Arge","year":"1998","journal-title":"Proceedings of the International Conference on Very Large Databases"},{"key":"2026040314023131800_ref048","first-page":"685","article-title":"Theory and practice of I\/O-efficient algorithms for multidimensional batched searching problems","author":"Arge","year":"1998","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algo-rithms"},{"key":"2026040314023131800_ref049","first-page":"88","article-title":"Implementing I\/O-efficient data structures using TPIE","author":"Arge","year":"2002","journal-title":"Proceedings of the European Symposium on Algorithms"},{"key":"2026040314023131800_ref050","first-page":"346","article-title":"Two-dimensional indexability and optimal range search indexing","author":"Arge","year":"1999","journal-title":"Proceedings of the ACM Conference on Principles of Database Systems"},{"key":"2026040314023131800_ref051","first-page":"4052","article-title":"Optimal external memory planar point enclosure","author":"Arge","year":"2004","journal-title":"Proceedings of the European Symposium on Algorithms"},{"key":"2026040314023131800_ref052","first-page":"493","article-title":"Simplified external memory algorithms for planar DAGs","author":"Arge","year":"2004","journal-title":"Proceedings of the Scandinavian Workshop on Algorithmic Theory"},{"key":"2026040314023131800_ref053","first-page":"328","article-title":"External data structures for shortest path queries on planar digraphs","author":"Arge","year":"2005","journal-title":"Proceedings of the International Symposium on Algorithms and Computation"},{"key":"2026040314023131800_ref054","article-title":"I\/O-efficient algorithms for problems on grid-based terrains","author":"Arge","year":"2000","journal-title":"Workshop on Algorithm Engineering and Experimentation"},{"key":"2026040314023131800_ref055","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1145\/777412.777427","article-title":"I\/O-efficient topological sorting of planar DAGs","author":"Arge","year":"2003","journal-title":"Proceedings of the ACM Symposium on Parallel Algorithms and Architectures"},{"issue":"2","key":"2026040314023131800_ref056","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.comgeo.2003.04.001","article-title":"I\/O-efficient dynamic planar point location","volume":"29","author":"Arge","year":"2004","journal-title":"Computational Geometry"},{"key":"2026040314023131800_ref057","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-006-1208-z","article-title":"External-memory algorithms for processing line segments in geographic information systems","volume":"47","author":"Arge","year":"2007","journal-title":"Algorithmica"},{"issue":"6","key":"2026040314023131800_ref058","doi-asserted-by":"crossref","DOI":"10.1137\/S009753970240481X","article-title":"Optimal external memory interval management","volume":"32","author":"Arge","journal-title":"SIAM Journal on Computing"},{"key":"2026040314023131800_ref059","first-page":"261","article-title":"I\/O-efficient strong connectivity and depth-first search for directed planar graphs","author":"Arge","year":"2003","journal-title":"Proceedings of the IEEE Symposium on Foun-dations of Computer Science"},{"key":"2026040314023131800_ref060","first-page":"122","article-title":"Bounds on the separation of two parallel disk models","author":"Armen","year":"1996","journal-title":"Proceedings of the Workshop on Input\/Output in Parallel and Distributed Systems"},{"key":"2026040314023131800_ref061","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/978-3-540-73437-6_11","article-title":"A Lempel-Ziv text index on secondary stor-age","author":"Arroyuelo","year":"2007","journal-title":"Proceedings of the Symposium on Combinatorial Pattern Matching"},{"key":"2026040314023131800_ref062","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0020-0255(03)00181-6","article-title":"(Almost) optimal parallel block access for range queries","volume":"157","author":"Atallah","year":"2003","journal-title":"Information Sciences"},{"issue":"5","key":"2026040314023131800_ref063","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/BF00289146","article-title":"Expected behaviour of B+-trees under random inser-tions","volume":"26","author":"Baeza-Yates","year":"1989","journal-title":"Acta Informatica"},{"key":"2026040314023131800_ref064","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0304-3975(96)00061-8","article-title":"Bounded disorder: The effect of the index","volume":"168","author":"Baeza-Yates","year":"1996","journal-title":"Theoretical Computer Science"},{"key":"2026040314023131800_ref065","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1109\/69.87964","article-title":"Performance of B+-trees with partial expansions","volume":"1","author":"Baeza-Yates","year":"1989","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"2026040314023131800_ref066","author":"Baeza-Yates"},{"key":"2026040314023131800_ref067","first-page":"70","article-title":"Analysis of linear hashing revis-ited","volume":"5","author":"Baeza-Yates","year":"1998","journal-title":"Nordic Journal of Computing"},{"issue":"4","key":"2026040314023131800_ref068","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1016\/S0167-8191(97)00015-X","article-title":"Simple randomized mergesort on parallel disks","volume":"23","author":"Barve","year":"1997","journal-title":"Parallel Computing"},{"key":"2026040314023131800_ref069","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1006\/jagm.2000.1089","article-title":"Competitive analysis of buffer management algorithms","volume":"36","author":"Barve","year":"2000","journal-title":"Journal of Algorithms"},{"key":"2026040314023131800_ref070","first-page":"83","article-title":"Modeling and optimizing I\/O throughput of multiple disks on a bus","author":"Barve","year":"1999","journal-title":"Procedings of ACM SIGMETRICS Joint International Conference on Measurement and Modeling of Computer Systems"},{"key":"2026040314023131800_ref071","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1109\/SFFCS.1999.814599","article-title":"A theoretical framework for memory-adaptive algorithms","author":"Barve","year":"1999","journal-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science"},{"key":"2026040314023131800_ref072","first-page":"189","article-title":"A simple and efficient parallel disk mergesort","volume":"35","author":"Barve","year":"2002","journal-title":"ACM Trans. Computer Systems"},{"key":"2026040314023131800_ref073","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jagm.1998.0988","article-title":"Data structures for mobile data","volume":"31","author":"Basch","year":"1999","journal-title":"Journal of Algorithms"},{"key":"2026040314023131800_ref074","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288683","article-title":"Organization of large ordered indexes","volume":"1","author":"Bayer","year":"1972","journal-title":"Acta Informatica"},{"key":"2026040314023131800_ref075","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/320521.320530","article-title":"Prefix B-trees","volume":"2","author":"Bayer","year":"1977","journal-title":"ACM Transactions on Database Systems"},{"key":"2026040314023131800_ref076","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1007\/s007780050028","article-title":"An asymptotically optimal multiversion B-tree","volume":"5","author":"Becker","year":"1996","journal-title":"VLDB Journal"},{"key":"2026040314023131800_ref077","author":"Beckmann","year":"1990"},{"key":"2026040314023131800_ref078","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1147\/sj.52.0078","article-title":"A study of replacement algorithms for virtual storage comput-ers","volume":"5","author":"Belady","year":"1966","journal-title":"IBM Systems Journal"},{"issue":"2","key":"2026040314023131800_ref079","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/S0097539701389956","article-title":"Cache-oblivious B- trees","volume":"35","author":"Bender","year":"2005","journal-title":"SIAM Journal on Computing"},{"key":"2026040314023131800_ref080","first-page":"233","article-title":"Cache-oblivious string B-trees","author":"Bender","year":"2006","journal-title":"Proceedings of the ACM Conference on Principles of Database Systems"},{"key":"2026040314023131800_ref081","first-page":"228","article-title":"Concurrent cache-oblivious B-trees","author":"Bender","year":"2005","journal-title":"Proceedings of the ACM Symposium on Parallel Algorithms and Architectures"},{"issue":"6","key":"2026040314023131800_ref082","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/358841.358850","article-title":"Multidimensional divideand conquer","volume":"23","author":"Bentley","year":"1980","journal-title":"Communications of the ACM"},{"key":"2026040314023131800_ref083","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","article-title":"Decomposable searching problems I: Static-to- dynamic transformations","volume":"1","author":"Bentley","year":"1980","journal-title":"Journal of Algorithms"},{"key":"2026040314023131800_ref084","first-page":"216230","article-title":"Improving the query performance of high-dimensional index structures by bulk load operations","author":"Berchtold","year":"1998","journal-title":"Proceedings of the International Conference on Extending Database Technology"},{"key":"2026040314023131800_ref085","article-title":"Deterministic load balancing and dictionaries in the parallel disk model","author":"Berger","year":"2006","journal-title":"Proceedings of the ACM Symposium on Parallel Algorithms and Architectures"},{"issue":"4","key":"2026040314023131800_ref086","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1093\/comjnl\/46.4.358","article-title":"A hierarchical technique for constructing efficient declustering schemes for range queries","volume":"46","author":"Bhatia","year":"2003","journal-title":"The Computer Journal"},{"key":"2026040314023131800_ref087","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0304-3975(80)90018-3","article-title":"On the average number of rebalancing operations in weight-balanced trees","volume":"11","author":"Blum","year":"1980","journal-title":"Theoretical Computer Science"},{"key":"2026040314023131800_ref088","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/359842.359859","article-title":"A fast string searching algorithm","volume":"20","author":"Boyer","year":"1977","journal-title":"Communications of the ACM"},{"key":"2026040314023131800_ref089","first-page":"110","article-title":"External memory computational geometry revisited","author":"Breimann","year":"2002","journal-title":"Algorithms for Memory Hierarchies"},{"key":"2026040314023131800_ref090","article-title":"An experimental study of priority queues in external memory","volume":"5","author":"Brengel","journal-title":"ACM Journal of Experimental Algo- rithmics"},{"key":"2026040314023131800_ref091","first-page":"546","article-title":"Lower bounds for external memory dictio-naries","author":"Brodal","year":"2003","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref092","first-page":"107","article-title":"Worst-case efficient external-memory priority queues","author":"Brodal","year":"1998","journal-title":"Proceedings of the Scandinavian Workshop on Algorithmic Theory"},{"key":"2026040314023131800_ref093","first-page":"859","article-title":"On external memory graph traversal","author":"Buchsbaum","year":"2000","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref094","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/3-540-60220-8_78","article-title":"Topology B-trees and their applications","author":"Callahan","year":"1995","journal-title":"Proceedings of the Workshop on Algorithms and Data Structures"},{"key":"2026040314023131800_ref095","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1145\/235543.235544","article-title":"Implementation and performance of integrated application-controlled file caching, prefetching and disk scheduling","volume":"14","author":"Cao","year":"1996","journal-title":"ACM Transactions on Computer Systems"},{"key":"2026040314023131800_ref096","first-page":"544","article-title":"Towards an optimal bit-reversal permutation pro-gram","author":"Carter","year":"1998","journal-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science"},{"key":"2026040314023131800_ref097","first-page":"317","article-title":"Oblivious vs. distribution-based sorting: An experimental evaluation","author":"Chaudhry","year":"2005","journal-title":"Proceedings of the European Symposium on Algorithms"},{"key":"2026040314023131800_ref098","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1137\/0215051","article-title":"Filtering search: A new approach to query-answering","volume":"15","author":"Chazelle","year":"1986","journal-title":"SIAM Journal on Computing"},{"key":"2026040314023131800_ref099","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1145\/77600.77614","article-title":"Lower bounds for orthogonal range searching: I. The reporting case","volume":"37","author":"Chazelle","year":"1990","journal-title":"Journal of the ACM"},{"key":"2026040314023131800_ref100","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF02187875","article-title":"Linear space data structures for two types of range search","volume":"2","author":"Chazelle","year":"1987","journal-title":"Discrete and Computational Geometry"},{"key":"2026040314023131800_ref101","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1145\/176979.176981","article-title":"RAID: High-performance, reliable secondary storage","volume":"26","author":"Chen","year":"1994","journal-title":"ACM Computing Surveys"},{"key":"2026040314023131800_ref102","article-title":"Efficient indexing methods for probabilistic threshold queries over uncertain data","author":"Cheng","year":"2004","journal-title":"Pro-ceedings of the International Conference on Very Large Databases"},{"key":"2026040314023131800_ref103","article-title":"Efficient join processing over uncertain-valued attributes","author":"Cheng","year":"2006","journal-title":"Proceedings of the International ACM Conference on Information and Knowledge Management"},{"issue":"4","key":"2026040314023131800_ref104","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0925-7721(97)00020-5","article-title":"Experiments on the practical I\/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep","volume":"8","author":"Chiang","year":"1998","journal-title":"Computational Geometry: Theory and Applications"},{"key":"2026040314023131800_ref105","first-page":"139","article-title":"External-memory graph algorithms","author":"Chiang","year":"1995","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref106","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1090\/dimacs\/050\/14","article-title":"External memory techniques for isosurface extraction in scientific visualization","author":"Chiang","year":"1999","journal-title":"External Memory Algorithms and Visualization"},{"key":"2026040314023131800_ref107","author":"Chien"},{"key":"2026040314023131800_ref108","first-page":"735","article-title":"External-memory exactand approximate all-pairs shortest-paths in undirected graphs","author":"Chowdhury","year":"2005","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref109","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1109\/SFCS.2002.1181945","article-title":"Static optimality theorem for external memory string access","author":"Ciriani","year":"2002","journal-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science"},{"key":"2026040314023131800_ref110","first-page":"383391","article-title":"Efficient suffix trees on secondary storage","author":"Clark","year":"1996","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref111","article-title":"Applications of random sampling in compu-tational geometry, II","volume":"4","author":"Clarkson","journal-title":"Discrete and Computational Geometry"},{"key":"2026040314023131800_ref112","first-page":"105","article-title":"A fast and compact Web graph representation","author":"Claude","year":"2007","journal-title":"Proceedings of the International Symposium on String Processing and Information Retrieval"},{"key":"2026040314023131800_ref113","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1109\/HIPS.1998.665140","article-title":"ViC*: A compiler for virtual-memory C*","author":"Colvin","year":"1998","journal-title":"Proceedings of the International Workshop on High-Level Programming Models and Supportive Environments"},{"issue":"2","key":"2026040314023131800_ref114","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/356770.356776","article-title":"The ubiquitous B-Tree","volume":"11","author":"Comer","year":"1979","journal-title":"ACM Computing Surveys"},{"key":"2026040314023131800_ref115","author":"Corbett"},{"key":"2026040314023131800_ref116","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1145\/233557.233558","article-title":"The Vesta parallel file system","volume":"14","author":"Corbett","year":"1996","journal-title":"ACM Transactions on Computer Systems"},{"key":"2026040314023131800_ref117","first-page":"137","article-title":"FG: A framework generator for hiding latency in parallel programs running on clusters","author":"Cormen","year":"2004","journal-title":"Proceedings of the 17th International Conference on Parallel and Distributed Computing Systems"},{"key":"2026040314023131800_ref118","author":"Cormen","journal-title":"Introduction to Algorithms"},{"key":"2026040314023131800_ref119","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/S0167-8191(97)00114-2","article-title":"Performing out-of-core FFTs on parallel disk systems","volume":"24","author":"Cormen","year":"1998","journal-title":"Parallel Computing"},{"issue":"1","key":"2026040314023131800_ref120","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1137\/S0097539795283681","article-title":"Asymptotically tight bounds for performing BMMC permutations on parallel disk systems","volume":"28","author":"Cormen","year":"1999","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"2026040314023131800_ref121","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-001-0051-5","article-title":"A theoretical and experimental study on the construction of suffix arrays in external memory","volume":"32","author":"Crauser","year":"2002","journal-title":"Algorithmica"},{"key":"2026040314023131800_ref122","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1090\/dimacs\/050\/07","article-title":"I\/O- optimal computation of segment intersections","author":"Crauser","year":"1999","journal-title":"External Memory Algorithms and Visualization"},{"issue":"3","key":"2026040314023131800_ref123","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1142\/S0218195901000523","article-title":"Randomized external-memory algorithms for line segment intersection and other geometric problems","volume":"11","author":"Crauser","year":"2001","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"2026040314023131800_ref124","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1007\/3-540-48318-7_19","article-title":"LEDA-SM: Extending LEDA to secondary memory","author":"Crauser","year":"1999","journal-title":"Proceedings of the Workshop on Algorithm Engineering"},{"key":"2026040314023131800_ref125","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1145\/170036.170077","article-title":"Practical Prefetching Via Data Compression","author":"Curewitz","year":"1993","journal-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data"},{"issue":"3","key":"2026040314023131800_ref126","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1016\/0022-0000(93)90043-V","article-title":"Deterministic sorting in nearly logarithmic time on the hypercube and related computers","volume":"47","author":"Cypher","year":"1993","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314023131800_ref127","author":"Davidson","journal-title":"FG: Improving Parallel Programs and Parallel Programming Since 2003"},{"issue":"3","key":"2026040314023131800_ref128","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0925-7721(02)00112-8","article-title":"On R- trees with low query complexity","volume":"24","author":"de Berg","year":"2003","journal-title":"Computational Geometry"},{"key":"2026040314023131800_ref129","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03427-9","author":"de Berg","year":"1997","journal-title":"Computational Geometry Algorithms and Applications"},{"key":"2026040314023131800_ref130","first-page":"137","article-title":"MapReduce: Simplified data processing on large clusters","author":"Dean","year":"2004","journal-title":"Proceedings of the Symposium on Operating Systems Design and Implementation"},{"issue":"2","key":"2026040314023131800_ref131","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s00453-002-1009-y","article-title":"Efficient External Memory Algorithms by Simulating Coarse-Grained Parallel Algorithms","volume":"36","author":"Dehne","year":"2003","journal-title":"Algorithmica"},{"issue":"6","key":"2026040314023131800_ref132","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1007\/s00224-002-1066-2","article-title":"Bulk synchronous parallel algorithms for the external memory model","volume":"35","author":"Dehne","year":"2002","journal-title":"Theory of Computing Systems"},{"key":"2026040314023131800_ref133","author":"Dementiev","journal-title":"Algorithm Engineering for Large Data Sets"},{"key":"2026040314023131800_ref134","article-title":"Better external memory suffix array construction","author":"Dementiev","journal-title":"ACM Journal of Experimental Algorith- mics"},{"issue":"6","key":"2026040314023131800_ref135","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1002\/spe.844","article-title":"STXXL: Standard Template Library for XXL Data Sets","volume":"38","author":"Dementiev","year":"2008","journal-title":"Software \u2014 Practice and Experience"},{"key":"2026040314023131800_ref136","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1145\/777412.777435","article-title":"Asynchronous parallel disk sorting","author":"Dementiev","year":"2003","journal-title":"Proceedings of the ACM Symposium on Parallel Algorithms and Architectures"},{"key":"2026040314023131800_ref137","article-title":"Engineering an external memory minimum spanning tree algorithm","author":"Dementiev","year":"2004","journal-title":"Proceedings of IFIP Inter-national Conference on Theoretical Computer Science"},{"key":"2026040314023131800_ref138","author":"Demuth","journal-title":"Electronic data sorting"},{"key":"2026040314023131800_ref139","article-title":"Working sets past and present","author":"Denning","journal-title":"IEEE Transactions on Software Engineering"},{"key":"2026040314023131800_ref140","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1109\/PDIS.1991.183115","article-title":"Parallel sorting on a shared-nothing architecture using probabilistic splitting","author":"DeWitt","year":"1991","journal-title":"Proceedings of the International Conference on Parallel and Distributed Information Systems"},{"issue":"2","key":"2026040314023131800_ref141","doi-asserted-by":"crossref","DOI":"10.1007\/s00224-001-0002-1","article-title":"Blocking in parallel multisearch problems","volume":"34","author":"Dittrich","journal-title":"Theory of Computing Systems"},{"key":"2026040314023131800_ref142","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","article-title":"Making data structures persistent","volume":"38","author":"Driscoll","year":"1989","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314023131800_ref143","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1147\/rd.303.0230","article-title":"Key-sequence data sets on indelible storage","volume":"30","author":"Easton","year":"1986","journal-title":"IBM Journal of Research and Development"},{"key":"2026040314023131800_ref144","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1080\/00207168308803364","article-title":"A new approach to rectangle intersections, Part I","volume":"13","author":"Edelsbrunner","year":"1983","journal-title":"International Journal of Computer Mathematics"},{"key":"2026040314023131800_ref145","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1080\/00207168308803365","article-title":"A New approach to rectangle intersections, Part II","volume":"13","author":"Edelsbrunner","year":"1983","journal-title":"International Journal of Computer Mathematics"},{"key":"2026040314023131800_ref146","author":"Eltabakh"},{"key":"2026040314023131800_ref147","author":"Enbody"},{"key":"2026040314023131800_ref148"},{"issue":"5","key":"2026040314023131800_ref149","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/265910.265914","article-title":"Sparsification \u2014 a technique for speeding up dynamic graph algorithms","volume":"44","author":"Eppstein","year":"1997","journal-title":"Journal of the ACM"},{"key":"2026040314023131800_ref150","first-page":"755","article-title":"Lower bounds for external algebraic decision trees","author":"Erickson","year":"2005","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref151","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s007780050030","article-title":"The hBn-tree: A multi-attribute index supporting concurrency, recovery and node consolidation","volume":"6","author":"Evangelidis","year":"1997","journal-title":"VLDB Journal"},{"key":"2026040314023131800_ref152","first-page":"68","article-title":"External string sorting: Faster and cache oblivious","author":"Fagerberg","year":"2006","journal-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science"},{"issue":"3","key":"2026040314023131800_ref153","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1145\/320083.320092","article-title":"Extendible hashing \u2014 a fast access method for dynamic files","volume":"4","author":"Fagin","year":"1979","journal-title":"ACM Transactions on Database Systems"},{"issue":"6","key":"2026040314023131800_ref154","doi-asserted-by":"crossref","first-page":"987","DOI":"10.1145\/355541.355547","article-title":"On the sortingcomplexity of suffix tree construction","volume":"47","author":"Farach-Colton","year":"2000","journal-title":"Journal of the ACM"},{"issue":"1","key":"2026040314023131800_ref155","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1137\/S0097539799361701","article-title":"An approximate L1-difference algorithm for massive data streams","volume":"32","author":"Feigenbaum","year":"2002","journal-title":"SIAM Journal on Computing"},{"key":"2026040314023131800_ref156","volume":"1","author":"Feller","year":"1968","journal-title":"An Introduction to Probability Theory and its Applications"},{"key":"2026040314023131800_ref157","first-page":"373","article-title":"Fast string searching in secondary storage: Theoretical developments and experimental results","author":"Ferragina","year":"1996","journal-title":"Proceedings of the ACM- SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref158","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1145\/301970.301973","article-title":"The String B-tree: A new data structure for string search in external memory and its applications","volume":"46","author":"Ferragina","year":"1999","journal-title":"Journal of the ACM"},{"key":"2026040314023131800_ref159","article-title":"On searching compressed string collections cache-obliviously","author":"Ferragina","year":"2008","journal-title":"Proceedings of the ACM Conference on Principles of Database Systems"},{"issue":"4","key":"2026040314023131800_ref160","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1016\/S0022-0000(03)00028-X","article-title":"Twodimensional substring indexing","volume":"66","author":"Ferragina","year":"2003","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314023131800_ref161","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1006\/inco.1998.2733","article-title":"Dynamic dictionary matching in external mem-ory","volume":"146","author":"Ferragina","year":"1998","journal-title":"Information and Computation"},{"issue":"4","key":"2026040314023131800_ref162","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1145\/1082036.1082039","article-title":"Indexing compressed texts","volume":"52","author":"Ferragina","year":"2005","journal-title":"Journal of the ACM"},{"key":"2026040314023131800_ref163","article-title":"Compressed representations of sequences and full-text indexes","volume":"3","author":"Ferragina","journal-title":"ACM Transaction on Algorithms"},{"issue":"4","key":"2026040314023131800_ref164","first-page":"345","article-title":"On the performance evaluation of extendible hashing and trie searching","volume":"20","author":"jolet","year":"1983","journal-title":"Acta Informatica"},{"key":"2026040314023131800_ref165","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/978-1-4684-2001-2_10","article-title":"Permuting information in idealized two-level storage","author":"Floyd","year":"1972","journal-title":"Complexity of Computer Computations"},{"key":"2026040314023131800_ref166","author":"Frakes"},{"issue":"4","key":"2026040314023131800_ref167","doi-asserted-by":"crossref","first-page":"788","DOI":"10.1016\/j.jcss.2003.11.003","article-title":"Implicit B-Trees: A new data structure for the dictionary problem","volume":"68","author":"Franceschini","year":"2004","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314023131800_ref168","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1109\/SFFCS.1999.814600","article-title":"Cache-oblivious algorithms","author":"Frigo","year":"1999","journal-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science"},{"key":"2026040314023131800_ref169","first-page":"11","article-title":"Management of large amounts of data in interactive building walkthroughs","author":"Funkhouser","year":"1992","journal-title":"Proceedings of the ACM Symposium on Interactive 3D Graphics"},{"key":"2026040314023131800_ref170","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1145\/280277.280279","article-title":"Multidimensional access methods","volume":"30","author":"Gaede","year":"1998","journal-title":"ACM Computing Surveys"},{"key":"2026040314023131800_ref171","first-page":"1263","article-title":"Generating representative synthetic workloads: An unsolved problem","author":"Ganger","year":"1995","journal-title":"Proceedings of the Computer Measurement Group Conference"},{"key":"2026040314023131800_ref172","author":"Gardner"},{"key":"2026040314023131800_ref173","doi-asserted-by":"crossref","first-page":"905","DOI":"10.1145\/358728.358741","article-title":"An effective way to represent quadtrees","volume":"25","author":"Gargantini","year":"1982","journal-title":"Communications of the ACM"},{"key":"2026040314023131800_ref174","article-title":"Bulk operations for space-partitioning trees","author":"Ghanem","year":"2004","journal-title":"Proceedings of IEEE International Conference on Data Engineering"},{"key":"2026040314023131800_ref175","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1145\/242223.242300","article-title":"Report of the working group on storage I\/O issues in large-scale computing","volume":"28","author":"Gibson","year":"1996","journal-title":"ACM Computing Surveys"},{"key":"2026040314023131800_ref176","first-page":"78","article-title":"Similarity search in high dimensions via hashing","author":"Gionis","year":"1999","journal-title":"Proceedings of the International Conference on Very Large Databases"},{"key":"2026040314023131800_ref177","first-page":"26","article-title":"Proximity search in databases","author":"Goldman","year":"1998","journal-title":"Proceedings of the International Conference on Very Large Databases"},{"key":"2026040314023131800_ref178","first-page":"80","article-title":"A compressed text index on secondary mem-ory","author":"Gonzalez","year":"2007","journal-title":"Proceedings of the International Workshop on Combinatorial Algo-rithms"},{"key":"2026040314023131800_ref179","author":"Goodrich"},{"key":"2026040314023131800_ref180","author":"\u201cGoogle Earth online database of satellite images,\u201d"},{"key":"2026040314023131800_ref181","first-page":"143","article-title":"CRB-tree: An efficient indexing scheme for range-aggregate queries","author":"Govindarajan","year":"2003","journal-title":"Proceedings of the International Conference on Database Theory"},{"key":"2026040314023131800_ref182","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/s00453-005-1197-3","article-title":"I\/O-efficient well-separated pair decomposition and its applications","volume":"45","author":"Govindarajan","year":"2006","journal-title":"Algorithmica"},{"key":"2026040314023131800_ref183","first-page":"606","article-title":"An implementationand performance analysis of spatial data access methods","author":"Greene","year":"1989","journal-title":"Proceedings of IEEE International Conference on Data Engineering"},{"key":"2026040314023131800_ref184","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1145\/339331.339354","article-title":"Modeling and performance of MEMS-based storage devices","author":"Griffin","year":"2000","journal-title":"Procedings of ACM SIGMETRICS Joint International Conference on Measurement and Modeling of Computer Systems"},{"key":"2026040314023131800_ref185","article-title":"High-order entropy-compressed text indexes","author":"Grossi","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algo-rithms"},{"key":"2026040314023131800_ref186","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/dimacs\/050\/04","article-title":"Efficient cross-trees for external memory","author":"Grossi","year":"1999","journal-title":"External Memory Algorithms and Visualization"},{"issue":"1","key":"2026040314023131800_ref187","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.1999.2811","article-title":"Efficient splittingand merging algorithms for order decomposable problems","volume":"154","author":"Grossi","year":"1999","journal-title":"Information and Computation"},{"key":"2026040314023131800_ref188","author":"Gupta"},{"key":"2026040314023131800_ref189","author":"Gusfield","journal-title":"Algorithms on Strings, Trees, and Sequences"},{"key":"2026040314023131800_ref190","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1145\/971697.602266","article-title":"R-trees: A dynamic index structure for spatial searching","author":"Guttman","year":"1984","journal-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data"},{"key":"2026040314023131800_ref191","first-page":"580","article-title":"I\/O-efficient algorithms on near-planar graphs","author":"Haverkort","year":"2006","journal-title":"Proceedings of the Latin American Theoretical Informatics Sym-posium"},{"key":"2026040314023131800_ref192","first-page":"52","article-title":"Terracost: A versatile and scalable approach to computing least-cost-path surfaces for massive grid-based terrains","author":"Hazel","year":"2006","journal-title":"Proceedings of the ACM Symposium on Applied Computing"},{"key":"2026040314023131800_ref193","first-page":"249","article-title":"On the analysis of indexing schemes","author":"Hellerstein","year":"1997","journal-title":"Proceedings of the ACM Symposium on Principles of Database Systems"},{"issue":"12-2","key":"2026040314023131800_ref194","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/BF01185210","article-title":"Coding techniques for handling failures in large disk arrays","volume":"12","author":"Hellerstein","year":"1994","journal-title":"Algorithmica"},{"key":"2026040314023131800_ref195","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1090\/dimacs\/050\/05","article-title":"Computing on data streams","author":"Henzinger","year":"1999","journal-title":"External Memory Algorithms and Visualization"},{"issue":"4","key":"2026040314023131800_ref196","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/BF01936137","article-title":"Implementation of the grid file: Design concepts and experience","volume":"25","author":"Hinrichs","year":"1985","journal-title":"BIT"},{"key":"2026040314023131800_ref197","author":"Hon"},{"key":"2026040314023131800_ref198","doi-asserted-by":"crossref","DOI":"10.1145\/1378533.1378593","article-title":"Tight competitive ratios for parallel disk prefetching and caching","author":"Hon","year":"2008","journal-title":"Proceedings of the ACM Symposium on Parallel Algorithms and Architectures"},{"key":"2026040314023131800_ref199","first-page":"326","article-title":"I\/O complexity: The red-blue pebble game","author":"Hong","year":"1981","journal-title":"Proceedings of the ACM Symposium on Theory of Computing"},{"key":"2026040314023131800_ref200","author":"Hutchinson","year":"1997"},{"issue":"1","key":"2026040314023131800_ref201","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0166-218X(02)00217-2","article-title":"An external memory data structure for shortest path queries","volume":"126","author":"Hutchinson","year":"2003","journal-title":"Discrete Applied Mathematics"},{"issue":"6","key":"2026040314023131800_ref202","doi-asserted-by":"crossref","first-page":"1443","DOI":"10.1137\/S0097539703431573","article-title":"Duality between prefetching and queued writing with parallel disks","volume":"34","author":"Hutchinson","year":"2005","journal-title":"SIAM Journal on Computing"},{"key":"2026040314023131800_ref203","first-page":"618","article-title":"Locality-preserving hashing in multidimensional spaces","author":"Indyk","year":"1997","journal-title":"Proceedings of the ACM Symposium on Theory of Computing"},{"key":"2026040314023131800_ref204","doi-asserted-by":"crossref","DOI":"10.1145\/378580.378648","article-title":"Optimal prefetchingand caching for parallel I\/O systems","author":"Kallahalla","year":"2001","journal-title":"Proceedings of the ACM Symposium on Parallel Algorithms and Architectures"},{"issue":"4","key":"2026040314023131800_ref205","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/s00453-004-1129-7","article-title":"Optimal read-once parallel disk scheduling","volume":"43","author":"Kallahalla","year":"2005","journal-title":"Algorithmica"},{"key":"2026040314023131800_ref206","first-page":"490","article-title":"On packing R-trees","author":"Kamel","year":"1993","journal-title":"Proceedings of the International ACM Conference on Information and Knowledge Management"},{"key":"2026040314023131800_ref207","first-page":"500","article-title":"Hilbert R-tree: An improved R-tree using frac-tals","author":"Kamel","year":"1994","journal-title":"Proceedings of the International Conference on Very Large Databases"},{"key":"2026040314023131800_ref208","author":"Kamel"},{"issue":"1","key":"2026040314023131800_ref209","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1006\/jcss.1995.1051","article-title":"Constraint query lan-guages","volume":"51","author":"Kanellakis","year":"1995","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"2026040314023131800_ref210","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1006\/jcss.1996.0043","article-title":"Indexing for data models with constraints and classes","volume":"52","author":"Kanellakis","year":"1996","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314023131800_ref211","first-page":"257","article-title":"Optimal dynamic range searching in non-replicating index structures","author":"Kanth","year":"1999","journal-title":"Proceedings of the International Conference on Database Theory"},{"key":"2026040314023131800_ref212","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-36574-5_7","article-title":"Full-text indexes in external memory","author":"K\u00e4rkk\u00e4inen","year":"2003","journal-title":"Algorithms for Memory Hierarchies"},{"key":"2026040314023131800_ref213","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-36574-5_4","article-title":"Elementary graph algorithms in external memory","author":"Katriel","year":"2003","journal-title":"Algorithms for Memory Hierarchies"},{"key":"2026040314023131800_ref214","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/11940128_10","article-title":"Offline Sorting Buffers On Line","author":"Khandekar","year":"2006","journal-title":"Proceedings of the International Symposium on Algorithms and Computation"},{"key":"2026040314023131800_ref215","author":"Khuller"},{"key":"2026040314023131800_ref216","doi-asserted-by":"crossref","first-page":"978","DOI":"10.1109\/TC.1986.1676699","article-title":"Synchronized disk interleaving","volume":"35","author":"Kim","year":"1986","journal-title":"IEEE Transactions on Computers"},{"issue":"4","key":"2026040314023131800_ref217","doi-asserted-by":"crossref","first-page":"1051","DOI":"10.1137\/S0097539797326976","article-title":"Near-optimal parallel prefetching and caching","volume":"29","author":"Kimbrel","year":"2000","journal-title":"SIAM Journal on Computing"},{"key":"2026040314023131800_ref218","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0215021","article-title":"The ultimate planar convex hull algo-rithm?","volume":"15","author":"Kirkpatrick","year":"1986","journal-title":"SIAM Journal on Computing"},{"key":"2026040314023131800_ref219","article-title":"Searching in compressed dictionaries","author":"Klein","year":"2002","journal-title":"Proceedings of the Data Compression Conference"},{"key":"2026040314023131800_ref220","author":"Knuth","journal-title":"Sorting and Searching"},{"key":"2026040314023131800_ref221","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-46611-8","author":"Knuth","year":"1999","journal-title":"MMIXware"},{"key":"2026040314023131800_ref222","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","article-title":"Fast pattern matching in strings","volume":"6","author":"Knuth","year":"1977","journal-title":"SIAM Journal on Computing"},{"key":"2026040314023131800_ref223","first-page":"261","article-title":"On indexing mobile objects","author":"Kollios","year":"1999","journal-title":"Proceedings of the ACM Symposium on Principles of Database Systems"},{"key":"2026040314023131800_ref224","first-page":"52","article-title":"Tight bounds for 2-dimensional indexing schemes","author":"Koutsoupias","year":"1998","journal-title":"Proceedings of the ACM Symposium on Principles of Database Systems"},{"key":"2026040314023131800_ref225","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-36574-5_10","article-title":"An overview of cache optimizaiton techniques and cache-aware numerical algorithms","author":"Kowarschik","year":"2003","journal-title":"Algorithms for Memory Hierarchies"},{"key":"2026040314023131800_ref226","doi-asserted-by":"crossref","first-page":"1617","DOI":"10.1137\/S0097539794261817","article-title":"Optimal prediction for prefetching in the worst case","volume":"27","author":"Krishnan","year":"1998","journal-title":"SIAM Journal on Computing"},{"key":"2026040314023131800_ref227","first-page":"169","article-title":"Improved algorithmsand data structures for solving graph problems in external memory","author":"Kumar","year":"1996","journal-title":"Proceedings of the IEEE Symposium on Parallel and Distributed Processing"},{"key":"2026040314023131800_ref228","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF00263927","article-title":"Storage utilization in B*-trees with a generalized overflow technique","volume":"19","author":"K\u00fcspert","year":"1983","journal-title":"Acta Informatica"},{"key":"2026040314023131800_ref229","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1145\/319758.319763","article-title":"Performance analysis of linear hashing with partial expan-sions","volume":"7","author":"Larson","year":"1982","journal-title":"ACM Transactions on Database Systems"},{"key":"2026040314023131800_ref230","author":"Laurini","journal-title":"Fundamentals of Spatial Information Systems"},{"key":"2026040314023131800_ref231","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1145\/319628.319663","article-title":"Efficient locking for concurrent operations on B-trees","volume":"6","author":"Lehman","year":"1981","journal-title":"ACM Transactions on Database Systems"},{"key":"2026040314023131800_ref232","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1109\/TC.1985.5009385","article-title":"Tight bounds on the complexity of parallel sorting","volume":"C-34","author":"Leighton","year":"1985","journal-title":"IEEE Transactions on Computers"},{"issue":"2","key":"2026040314023131800_ref233","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1006\/jcss.1997.1473","article-title":"Efficient out-of-core algorithms for linear relaxation using blocking covers","volume":"54","author":"Leiserson","year":"1997","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314023131800_ref234","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1080\/10637199608915543","article-title":"Models and resource metrics for parallel and distributed computation","volume":"8","author":"Li","year":"1996","journal-title":"Parallel Algorithms and Applications"},{"key":"2026040314023131800_ref235","first-page":"212","article-title":"Linear hashing: A new tool for files and tables addressing","author":"Litwin","year":"1980","journal-title":"Proceedings of the International Conference on Very Large Databases"},{"key":"2026040314023131800_ref236","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1109\/MS.1987.230092","article-title":"A new method for fast data searches with keys","volume":"4","author":"Litwin","year":"1987","journal-title":"IEEE Software"},{"issue":"4","key":"2026040314023131800_ref237","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1145\/49346.50067","article-title":"A simple bounded disorder file organization with good perfor-mance","volume":"13","author":"Lomet","year":"1988","journal-title":"ACM Transactions on Database Systems"},{"issue":"4","key":"2026040314023131800_ref238","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1145\/99935.99949","article-title":"The hB-tree: A multiattribute indexing method with good guaranteed performance","volume":"15","author":"Lomet","year":"1990","journal-title":"ACM Transactions on Database Systems"},{"issue":"3","key":"2026040314023131800_ref239","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1007\/s007780050042","article-title":"Concurrency and recovery for index trees","volume":"6","author":"Lomet","year":"1997","journal-title":"VLDB Journal"},{"key":"2026040314023131800_ref240","first-page":"244","article-title":"I\/O-efficient batched range counting and its applications to proximity problems","author":"Lukovszki","year":"2001","journal-title":"Foundations of Software Tech-nology and Theoretical Computer Science"},{"key":"2026040314023131800_ref241","first-page":"89","article-title":"I\/O-efficient algorithms for graphs of bounded treewidth","author":"Maheshwari","year":"2001","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algo-rithms"},{"key":"2026040314023131800_ref242","first-page":"372","article-title":"I\/O-Optimal Algorithms for Planar Graphs Using Separators","author":"Maheshwari","year":"2002","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref243","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-36574-5_3","article-title":"A survey of techniques for designing I\/O-efficient algorithms","author":"Maheshwari","year":"2003","journal-title":"Algorithms for Memory Hierarchies"},{"key":"2026040314023131800_ref244","doi-asserted-by":"crossref","first-page":"47","DOI":"10.7155\/jgaa.00082","article-title":"I\/O-optimal algorithms for outerplanar graphs","volume":"8","author":"Maheshwari","year":"2004","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"2026040314023131800_ref245","first-page":"681","article-title":"Advantages of backward searching \u2014 efficient secondary memory and distributed implementation of compressed suffix arrays","author":"Makinen","year":"2004","journal-title":"Proceedings of the International Symposium on Algorithms and Computation"},{"key":"2026040314023131800_ref246","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","article-title":"Suffix arrays: A new method for on-line string searches","volume":"22","author":"Manber","year":"1993","journal-title":"SIAM Journal on Computing"},{"key":"2026040314023131800_ref247","author":"Manber"},{"key":"2026040314023131800_ref248","article-title":"Spiral storage: Incrementally augmentable hash addressed storage","author":"Martin"},{"key":"2026040314023131800_ref249","first-page":"839","article-title":"Efficient bundle sorting","author":"Matias","year":"2000","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"issue":"2","key":"2026040314023131800_ref250","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","article-title":"A space-economical suffix tree construction algorithm","volume":"23","author":"McCreight","year":"1976","journal-title":"Journal of the ACM"},{"key":"2026040314023131800_ref251","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1137\/0214021","article-title":"Priority Search Trees","volume":"14","author":"McCreight","year":"1985","journal-title":"SIAM Journal on Computing"},{"key":"2026040314023131800_ref252","first-page":"723","article-title":"External-memory breadth-first search with sublinear I\/O","author":"Mehlhorn","year":"2002","journal-title":"Proceedings of the European Symposium on Algorithms"},{"key":"2026040314023131800_ref253","article-title":"Analysis of extendible hashing","author":"Mendelson","journal-title":"IEEE Transactions on Software Engineering"},{"key":"2026040314023131800_ref254","first-page":"87","article-title":"External memory BFS on undirected graphs with bounded degree","author":"Meyer","year":"2001","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref255","first-page":"551","article-title":"On dynamic breadth-first search in external-memory","author":"Meyer","year":"2008","journal-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science"},{"key":"2026040314023131800_ref256","article-title":"On trade-offs in external-memory diameter approximation","author":"Meyer","journal-title":"Proceedings of the Scandinavian Workshop on Algorithm Theory"},{"key":"2026040314023131800_ref257","author":"Meyer","year":"2003"},{"key":"2026040314023131800_ref258","first-page":"435","article-title":"I\/O-efficient undirected shortest paths","author":"Meyer","year":"2003","journal-title":"Proceedings of the European Symposium on Algorithms"},{"key":"2026040314023131800_ref259","article-title":"I\/O-efficient undirected shortest paths with unbounded weights","author":"Meyer","journal-title":"Proceedings of the European Symposium on Algorithms"},{"key":"2026040314023131800_ref260","first-page":"392","article-title":"ARIES\/KVL: A key-value locking method for concurrency control of multiaction transactions on B-tree indices","author":"Mohan","year":"1990","journal-title":"Proceedings of the International Conference on Very Large Databases"},{"key":"2026040314023131800_ref261","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1145\/321479.321481","article-title":"Patricia: Practical algorithm to retrieve information coded in alphanumeric","volume":"15","author":"Morrison","year":"1968","journal-title":"Journal of the ACM"},{"key":"2026040314023131800_ref262","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1006\/jpdc.1996.0130","article-title":"Characterizing concurrency control performance for the PIOUS parallel file system","volume":"38","author":"Moyer","year":"1996","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"2026040314023131800_ref263","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1093\/comjnl\/28.3.330","article-title":"Spiral storage: Efficient dynamic hashing with constant perfor-mance","volume":"28","author":"Mullin","year":"1985","journal-title":"The Computer Journal"},{"key":"2026040314023131800_ref264","first-page":"687","article-title":"I\/O-complexity of graph algorithms","author":"Munagala","year":"1999","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref265","volume":"1","author":"Muthukrishnan","year":"2005","journal-title":"Data Streams: Algorithms and Applications"},{"issue":"1","key":"2026040314023131800_ref266","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S1570-8667(03)00066-2","article-title":"Indexing text using the Ziv-Lempel trie","volume":"2","author":"Navarro","year":"2004","journal-title":"Journal of Discrete Algorithms"},{"issue":"1","key":"2026040314023131800_ref267","doi-asserted-by":"crossref","DOI":"10.1145\/1216370.1216372","article-title":"Compressed full-text indexes","volume":"39","author":"Navarro","journal-title":"ACM Computing Surveys"},{"key":"2026040314023131800_ref268","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1145\/348.318586","article-title":"The grid file: An adaptable, symmetric multi-key file structure","volume":"9","author":"Nievergelt","year":"1984","journal-title":"ACM Transactions on Database Systems"},{"key":"2026040314023131800_ref269","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0202005","article-title":"Binary search tree of bounded balance","volume":"2","author":"Nievergelt","year":"1973","journal-title":"SIAM Journal on Computing"},{"key":"2026040314023131800_ref270","first-page":"153","article-title":"Spatial data structures: Concepts and design choices","author":"Nievergelt","year":"1997","journal-title":"Algorithmic Foundations of GIS"},{"key":"2026040314023131800_ref271","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01940646","article-title":"Blocking for external graph searching","volume":"16","author":"Nodine","year":"1996","journal-title":"Algorithmica"},{"key":"2026040314023131800_ref272","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1109\/12.83622","article-title":"I\/O overhead and parallel VLSI architectures for lattice computations","volume":"40","author":"Nodine","year":"1991","journal-title":"IEEE Transactions on Commu-nications"},{"key":"2026040314023131800_ref273","first-page":"120","article-title":"Deterministic distribution sort in shared and distributed memory multiprocessors","author":"Nodine","year":"1993","journal-title":"Proceedings of the ACM Symposium on Parallel Algorithms and Architectures"},{"key":"2026040314023131800_ref274","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1145\/210332.210343","article-title":"Greed Sort: An optimal sorting algorithm for multiple disks","volume":"42","author":"Nodine","year":"1995","journal-title":"Journal of the ACM"},{"key":"2026040314023131800_ref275","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/BF01185680","article-title":"The SB-tree. An index-sequential structure for high-performance sequential access","volume":"29","author":"O\u2019Neil","year":"1992","journal-title":"Acta Informatica"},{"key":"2026040314023131800_ref276","first-page":"294305","article-title":"Redundancy in spatial databases","author":"Orenstein","year":"1989","journal-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data"},{"key":"2026040314023131800_ref277","first-page":"181","article-title":"A class of data structures for associative searching","author":"Orenstein","year":"1984","journal-title":"Proceedings of the ACM Conference on Principles of Database Systems"},{"key":"2026040314023131800_ref278","author":"Overmars","journal-title":"The design of dynamic data structures"},{"key":"2026040314023131800_ref279","first-page":"618629","article-title":"Memory-adaptive external sorts","author":"Pang","journal-title":"Proceedings of the International Conference on Very Large Databases"},{"key":"2026040314023131800_ref280","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1145\/170036.170051","article-title":"Partially preemptive hash joins","author":"Pang","year":"1993","journal-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data"},{"key":"2026040314023131800_ref281","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1016\/S0167-8191(97)00013-6","article-title":"PI\/OT: Parallel I\/O templates","volume":"23","author":"Parsons","year":"1997","journal-title":"Parallel Computing"},{"key":"2026040314023131800_ref282","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1145\/235968.233338","article-title":"Partition based spatial-merge join","author":"Patel","year":"1996","journal-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data"},{"key":"2026040314023131800_ref283","first-page":"395","article-title":"Novel approaches to the indexing of moving object trajectories","author":"Pfoser","year":"2000","journal-title":"Proceedings of the International Conference on Very Large Databases"},{"key":"2026040314023131800_ref284","author":"Preparata","journal-title":"Computational Geometry"},{"key":"2026040314023131800_ref285","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-45072-6_4","article-title":"Bkd-tree: A dynamic scalable kd-tree","author":"Procopiuc","year":"2003","journal-title":"Proceedings of the International Symposium on Spatial and Temporal Databases"},{"key":"2026040314023131800_ref286","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1007\/11880561_11","article-title":"Inverted files versus suffix arrays for locating patterns in primary memory","author":"Puglisi","year":"2006","journal-title":"Proceedings of the International Symposium on String Processing Information Retrieval"},{"key":"2026040314023131800_ref287","article-title":"Adapting radix sort to the memory hierarchy","author":"Rahman","journal-title":"Workshop on Algorithm Engineering and Experimentation"},{"key":"2026040314023131800_ref288","first-page":"233","article-title":"Succinct indexable dictionaries with applications to encoding k-ary trees and multisets","author":"Raman","year":"2002","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref289","first-page":"25","article-title":"Path caching: A technique for optimal external searching","author":"Ramaswamy","year":"1994","journal-title":"Proceedings of the ACM Conference on Principles of Database Systems"},{"key":"2026040314023131800_ref290","first-page":"78","article-title":"Cache conscious indexing for decision-support in main memory","author":"Rao","year":"1999","journal-title":"Proceedings of the International Conference on Very Large Databases"},{"key":"2026040314023131800_ref291","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1145\/335191.335449","article-title":"Making B+-trees cache conscious in main memory","author":"Rao","year":"2000","journal-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data"},{"key":"2026040314023131800_ref292","first-page":"62","article-title":"Active storage for large-scale data mining and multimedia","author":"Riedel","year":"1998","journal-title":"Proceedings of the International Conference on Very Large Databases"},{"key":"2026040314023131800_ref293","first-page":"10","article-title":"The k-d-b-tree: A search structure for large multidimensional dynamic indexes","author":"Robinson","year":"1981","journal-title":"Proceedings of the ACM Conference on Principles of Database Systems"},{"key":"2026040314023131800_ref294","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1145\/244804.244807","article-title":"Using the SimOS machine simulator to study complex computer systems","volume":"7","author":"Rosenblum","year":"1997","journal-title":"ACM Transactions on Modeling and Computer Simulation"},{"key":"2026040314023131800_ref295","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1109\/2.268881","article-title":"An introduction to disk drive modeling","author":"Ruemmler","year":"1994","journal-title":"IEEE Computer"},{"key":"2026040314023131800_ref296","first-page":"336","article-title":"Disk striping","author":"Salem","year":"1986","journal-title":"Proceedings of IEEE International Conference on Data Engineering"},{"key":"2026040314023131800_ref297","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1145\/335191.335427","article-title":"Indexing the positions of continuously moving objects","author":"Saltenis","year":"2000","journal-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data"},{"key":"2026040314023131800_ref298","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1145\/319806.319816","article-title":"Comparison of access methods for timeevolving data","volume":"31","author":"Salzberg","year":"1999","journal-title":"ACM Computing Surveys"},{"key":"2026040314023131800_ref299","author":"Samet","journal-title":"Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS"},{"key":"2026040314023131800_ref300","author":"Samet","journal-title":"The Design and Analysis of Spatial Data Structures"},{"key":"2026040314023131800_ref301","first-page":"44","article-title":"A lower bound theorem for indexing schemes and its application to multidimensional range queries","author":"Samoladas","year":"1998","journal-title":"Proceedings of the ACM Symposium on Principles of Database Systems"},{"issue":"7","key":"2026040314023131800_ref302","first-page":"1","article-title":"Fast priority queues for cached memory","volume":"5","author":"Sanders","year":"2000","journal-title":"ACM Journal of Experimental Algorithmics"},{"issue":"5","key":"2026040314023131800_ref303","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/S0167-8191(02)00092-3","article-title":"Reconciling simplicityand realism in parallel disk models","volume":"28","author":"Sanders","year":"2002","journal-title":"Parallel Computing"},{"issue":"1","key":"2026040314023131800_ref304","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s00453-002-0987-0","article-title":"Fast concurrent access to parallel disks","volume":"35","author":"Sanders","year":"2002","journal-title":"Algorithmica"},{"key":"2026040314023131800_ref305","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1007\/BFb0030842","article-title":"Extending the Hong-Kung model to memory hierarchies","author":"Savage","year":"1995","journal-title":"Proceedings of the International Conference on Computing and Combinatorics"},{"key":"2026040314023131800_ref306","first-page":"117","article-title":"Parallelism in space-time tradeoffs","author":"Savage","year":"1987","journal-title":"Advances in Computing Research"},{"key":"2026040314023131800_ref307","first-page":"1","article-title":"Designing computer systems with MEMS-based storage","author":"Schlosser","year":"2000","journal-title":"Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems"},{"issue":"2","key":"2026040314023131800_ref308","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF00130709","article-title":"Multidimensional array I\/O in Panda 1.0","volume":"10","author":"Seamons","year":"1996","journal-title":"Journal of Supercomputing"},{"key":"2026040314023131800_ref309","first-page":"590","article-title":"The buddy-tree: An efficient and robust access method for spatial data base systems","author":"Seeger","year":"1990","journal-title":"Proceedings of the International Conference on Very Large Databases"},{"key":"2026040314023131800_ref310","first-page":"249","article-title":"File system logging versus clustering: A performance comparison","author":"Seltzer","year":"1995","journal-title":"Proceedings of the Annual USENIX Technical Conference"},{"issue":"6","key":"2026040314023131800_ref311","doi-asserted-by":"crossref","first-page":"828","DOI":"10.1145\/602220.602225","article-title":"Towards a theory of cache-efficient algorithms","volume":"49","author":"Sen","year":"2002","journal-title":"Journal of the ACM"},{"key":"2026040314023131800_ref312","first-page":"255","article-title":"Online algorithms for prefetching and caching on parallel disks","author":"Shah","year":"2004","journal-title":"Proceedings of the ACM Symposium on Parallel Algorithms and Architectures"},{"key":"2026040314023131800_ref313","first-page":"217","article-title":"On competitive online read-many parallel disks scheduling","author":"Shah","year":"2005","journal-title":"Proceedings of the ACM Symposium on Parallel Algorithms and Architectures"},{"key":"2026040314023131800_ref314","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1145\/277851.277906","article-title":"An analytic behavior model for disk drives with readahead caches and request reordering","author":"Shriver","year":"1998","journal-title":"Procedings of ACM SIGMETRICS Joint International Conference on Measurement and Modeling of Computer Systems"},{"key":"2026040314023131800_ref315","article-title":"An introduction to parallel I\/O models and algorithms","author":"Shriver","journal-title":"Input\/Output in Parallel and Distributed Computer Sys-tems"},{"key":"2026040314023131800_ref316","article-title":"An API for choreographing data accesses","author":"Shriver"},{"key":"2026040314023131800_ref317","article-title":"From parallel to external list ranking","author":"Sibeyn"},{"issue":"2","key":"2026040314023131800_ref318","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.jalgor.2005.02.002","article-title":"External selection","volume":"58","author":"Sibeyn","year":"2006","journal-title":"Journal of Algorithms"},{"key":"2026040314023131800_ref319","first-page":"229240","article-title":"BSP-like external-memory computation","author":"Sibeyn","journal-title":"Proceedings of the Italian Conference on Algorithms and Complexity"},{"key":"2026040314023131800_ref320","article-title":"Improving suffix array locality for fast pattern matching on disk","author":"Sinha","year":"2008","journal-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data"},{"issue":"5","key":"2026040314023131800_ref321","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1093\/comjnl\/34.5.397","article-title":"An adaptive overflow technique to defer splitting in B-trees","volume":"34","author":"Srinivasan","year":"1991","journal-title":"The Computer Journal"},{"key":"2026040314023131800_ref322","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1145\/773473.178260","article-title":"ATOM: A system for building customized program analysis tools","volume":"29","author":"Srivastava","year":"1994","journal-title":"ACM SIGPLAN Notices"},{"key":"2026040314023131800_ref323","first-page":"378","article-title":"The P-range tree: A new data structure for range searching in secondary memory","author":"Subramanian","year":"1995","journal-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314023131800_ref324","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/BF01941686","article-title":"Optimal cooperative search in fractional cascaded data structures","volume":"15","author":"Tamassia","year":"1996","journal-title":"Algorithmica"},{"key":"2026040314023131800_ref325","author":"\u201cTerraServer-USA: Microsoft\u2019s online database of satellite images,\u201d"},{"key":"2026040314023131800_ref326","first-page":"70","article-title":"Passion: Optimized I\/O for parallel applications","volume":"29","author":"Thakur","year":"1996","journal-title":"IEEE Computer"},{"key":"2026040314023131800_ref327","author":"\u201cTopologically Integrated Geographic Encoding and Referencing system, TIGER\/Line 1992 datafiles,\u201d"},{"key":"2026040314023131800_ref328","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1090\/dimacs\/050\/09","article-title":"A survey of out-of-core algorithms in numerical linear algebra","author":"Toledo","year":"1999","journal-title":"External Memory Algorithms and Visualization"},{"key":"2026040314023131800_ref329","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-36574-5_5","article-title":"I\/O-efficient algorithms for sparse graphs","author":"Toma","year":"2003","journal-title":"Algorithms for Memory Hierarchies"},{"key":"2026040314023131800_ref330","author":"TPIE User Manual and Reference, \u201cThe manual and software distribution,\u201d"},{"key":"2026040314023131800_ref331","article-title":"The input\/output complexity of transitive closure","volume":"3","author":"Ullman","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"2026040314023131800_ref332","article-title":"Planar point location for large data sets: To seek or not to seek","volume":"7","author":"Vahrenhold","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"2026040314023131800_ref333","author":"den"},{"key":"2026040314023131800_ref334","author":"van Kreveld"},{"key":"2026040314023131800_ref335","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1109\/69.599929","article-title":"An efficient multiversion access structure","volume":"9","author":"Varman","year":"1997","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"2026040314023131800_ref336","first-page":"192","article-title":"Efficient 3-D range searching in external memory","author":"Vengroff","year":"1996","journal-title":"Proceedings of the ACM Symposium on Theory of Computing"},{"key":"2026040314023131800_ref337","article-title":"I\/O-efficient scientific computation using TPIE","author":"Vengroff","journal-title":"Proceedings of NASA Goddard Conference on Mass Storage Sys-tems"},{"issue":"3","key":"2026040314023131800_ref338","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1147\/rd.443.0323","article-title":"The \u2018Millipede\u2019 \u2014 more than one thousand tips for future AFM data storage","volume":"44","author":"Vettiger","year":"2000","journal-title":"IBM Journal of Research and Development"},{"key":"2026040314023131800_ref339","first-page":"26","article-title":"Efficient memory access in large-scale computation","author":"Vitter","year":"1991","journal-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science"},{"key":"2026040314023131800_ref340","author":"Vitter","journal-title":"Notes"},{"key":"2026040314023131800_ref341","author":"Vitter"},{"key":"2026040314023131800_ref342","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1145\/1162349.1162352","article-title":"Distribution sort with randomized cycling","volume":"53","author":"Vitter","year":"2006","journal-title":"Journal of the ACM"},{"key":"2026040314023131800_ref343","doi-asserted-by":"crossref","first-page":"771","DOI":"10.1145\/234752.234753","article-title":"Optimal prefetching via data compression","volume":"43","author":"Vitter","year":"1996","journal-title":"Journal of the ACM"},{"key":"2026040314023131800_ref344","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1006\/jpdc.1993.1008","article-title":"Large-scale sorting in uniform memory hier-archies","volume":"17","author":"Vitter","year":"1993","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"12-2","key":"2026040314023131800_ref345","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/BF01185207","article-title":"Algorithms for parallel memory I: Two-level memories","volume":"12","author":"Vitter","year":"1994","journal-title":"Algorithmica"},{"issue":"12-2","key":"2026040314023131800_ref346","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/BF01185208","article-title":"Algorithms for parallel memory II: Hierarchical multilevel memories","volume":"12","author":"Vitter","year":"1994","journal-title":"Algorithmica"},{"key":"2026040314023131800_ref347","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1145\/304181.304199","article-title":"Approximate computation of multidimensional aggregates of sparse data using wavelets","author":"Vitter","year":"1999","journal-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data"},{"key":"2026040314023131800_ref348","first-page":"96","article-title":"Data cube approximation and histograms via wavelets","author":"Vitter","year":"1998","journal-title":"Proceedings of the International ACM Conference on Information and Knowledge Management"},{"key":"2026040314023131800_ref349","doi-asserted-by":"crossref","DOI":"10.1214\/lnms\/1196285404","article-title":"Scalable mining for classification rules in relational databases","author":"Wang","year":"2004","journal-title":"Herman Rubin Festschrift"},{"key":"2026040314023131800_ref350","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/3-540-47724-1_10","article-title":"Wavelet-based cost estimation for spatial queries","author":"Wang","year":"2001","journal-title":"Proceedings of the International Symposium on Spatial and Temporal Databases"},{"key":"2026040314023131800_ref351","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1109\/MASS.1995.528214","article-title":"The parallel I\/O architecture of the high-performance storage system (HPSS)","author":"Watson","year":"1995","journal-title":"Proceedings of the IEEE Symposium on Mass Storage Systems"},{"key":"2026040314023131800_ref352","first-page":"1","article-title":"Linear pattern matching algorithm","author":"Weiner","year":"1973","journal-title":"Proceedings of the IEEE Symposium on Switching and Automata Theory"},{"key":"2026040314023131800_ref353","first-page":"449","article-title":"Multilevel grid files \u2014 a dynamic hierarchical multidimensional file structure","author":"Whang","year":"1992","journal-title":"Proceedings of the International Symposium on Database Systems for Advanced Applications"},{"issue":"3","key":"2026040314023131800_ref354","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1145\/3828.3839","article-title":"Adding range restriction capability to dynamic data structures","volume":"32","author":"Willard","year":"1985","journal-title":"Journal of the ACM"},{"key":"2026040314023131800_ref355","author":"Witten","journal-title":"Managing Gigabytes: Compressing and Indexing Documents and Images"},{"key":"2026040314023131800_ref356","author":"Wolfson"},{"key":"2026040314023131800_ref357","first-page":"56","article-title":"Beyond core: Making parallel computer I\/O practical","author":"Womble","year":"1993","journal-title":"Proceedings of the DAGS Symposium on Parallel Computation"},{"key":"2026040314023131800_ref358","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1109\/TC.1981.1675790","article-title":"The universality of the shuffle-exchange network","volume":"C-30","author":"Wu","year":"1981","journal-title":"IEEE Transactions on Computers"},{"key":"2026040314023131800_ref359","first-page":"52","article-title":"Indexing continuously changing data with mean-variance tree","author":"Xia","year":"2005","journal-title":"Proceedings of the ACM Sympo-sium on Applied Computing"},{"key":"2026040314023131800_ref360","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/BF00289075","article-title":"On random 2-3 trees","volume":"9","author":"Yao","year":"1978","journal-title":"Acta Informatica"},{"key":"2026040314023131800_ref361","author":"Zdonik"},{"key":"2026040314023131800_ref362","author":"Zeh","journal-title":"I\/O-Efficient Algorithms for Shortest Path Related Problems"},{"key":"2026040314023131800_ref363","first-page":"376","article-title":"Dynamic memory adjustment for external mergesort","author":"Zhang","year":"1997","journal-title":"Proceedings of the International Conference on Very Large Databases"},{"key":"2026040314023131800_ref364","first-page":"514522","article-title":"Further computational geometry in secondary memory","author":"Zhu","year":"1994","journal-title":"Proceedings of the International Symposium on Algorithms and Computation"},{"key":"2026040314023131800_ref365","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable-rate coding","volume":"24","author":"Ziv","year":"1978","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Foundations and Trends\u00ae in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/2\/4\/305\/11150195\/0400000014en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/2\/4\/305\/11150195\/0400000014en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T18:03:26Z","timestamp":1775239406000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/fttcs\/article\/2\/4\/305\/1332198\/Algorithms-and-Data-Structures-for-External-Memory"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6,9]]},"references-count":365,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,6,9]]}},"URL":"https:\/\/doi.org\/10.1561\/0400000014","relation":{},"ISSN":["1551-305X","1551-3068"],"issn-type":[{"value":"1551-305X","type":"print"},{"value":"1551-3068","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6,9]]}}}