External memory algorithms and data structures: dealing with massive data

ABSTRACT

Data sets in large applications are often too massive to fit completely inside the computers 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 article we survey the state of the art in the design and analysis of external memory (or EM) algorithms and data structures, where the goal is to exploit locality 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. For the batched problem of sorting and related problems such as 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 (such as matrix multiplication and transposition), geometric data (such as finding intersections and constructing convex hulls), and graphs (such as list ranking, connected components, topological sorting, and shortest paths). 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 a convenient means in online data structures to make effective use of the data accessed from disk. We also reexamine 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 (e.g., text strings), or when the allocated amount of internal memory can change dynamically. Programming tools and environments are available for simplifying the EM programming task. During the course of the survey, 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 methods currently used in practice.

REFERENCES

• 1: ABEL, D. J. 1984. A B+-tree structure for large quadtrees. Computer Vision, Graphics, and Image Processing 27, 1 (July), 19-31.
• 2: James Abello , Adam L. Buchsbaum , Jeffery Westbrook, A Functional Approach to External Graph Algorithms, Proceedings of the 6th Annual European Symposium on Algorithms, p.332-343, August 24-26, 1998
• 3: Anurag Acharya , Mustafa Uysal , Joel Saltz, Active disks: programming model, algorithms and evaluation, ACM SIGPLAN Notices, v.33 n.11, p.81-91, Nov. 1998
• 4: M. Adler, New coding techniques for improved bandwidth utilization, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.173, October 14-16, 1996
• 5: AGARWAL,P.K.AND ERICKSON, J. 1999. Geometric range searching and its relatives. In B. Chazelle, J. E. Goodman, and R. Pollack, Eds, Advances in Discrete and Computational Geometry, Vol. 23 of Contemporary Mathematics, American Mathematical Society, Providence, RI, 1-56.
• 6: Pankaj K. Agarwal , Sariel Hal-Peled, Maintaining approximate extent measures of moving points, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.148-157, January 07-09, 2001, Washington, D.C., United States
• 7: Pankaj K. Agarwal , Lars Arge , Jeff Erickson, Indexing moving points (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.175-186, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335220]
• 8: Pankaj K. Agarwal , Lars Arge , Gerth Stølting Brodal , Jeffrey S. Vitter, I/O-efficient dynamic point location in monotone planar subdivisions, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.11-20, January 17-19, 1999, Baltimore, Maryland, United States
• 9: Pankaj K. Agarwal , Lars Arge , Jeff Erickson , Paolo G. Franciosa , Jeffry Scott Vitter, Efficient searching with linear constraints, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.169-178, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275506]
• 10: Pankaj K. Agarwal , Lars Arge , T. M. Murali , Kasturi R. Varadarajan , Jeffrey Scott Vitter, I/O-efficient algorithms for contour-line extraction and planar graph blocking, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.117-126, January 25-27, 1998, San Francisco, California, United States
• 11: Pankaj K. Agarwal , Lars Arge , Octavian Procopiuc , Jeffrey Scott Vitter, A Framework for Index Bulk Loading and Dynamization, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.115-127, July 08-12, 2001
• 12: Pankaj K. Agarwal , Mark de Berg , Joachim Gudmundsson , Mikael Hammar , Herman J. Haverkort, Box-trees and R-trees with near-optimal query time, Proceedings of the seventeenth annual symposium on Computational geometry, p.124-133, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378645]
• 13: Alok Aggarwal , C. Greg Plaxton, Optimal parallel sorting in multi-level storage, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.659-668, January 23-25, 1994, Arlington, Virginia, United States
• 14: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 15: A. Aggarwal , B. Alpern , A. Chandra , M. Snir, A model for hierarchical memory, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.305-314, January 1987, New York, New York, United States [doi>10.1145/28395.28428]
• 16: AGGARWAL, A., CHANDRA, A., AND SNIR, M. 1987b. Hierarchical memory with block transfer. In Proceedings of the IEEE Symposium on Foundations of Computer Science, Vol. 28 (Los Angeles), 204- 216.
• 17: M Ajtai , M Fredman , J Komlós, Hash functions for priority queues, Information and Control, v.63 n.3, p.217-225, Dec. 1986 [doi>10.1016/S0019-9958(84)80015-7]
• 18: ALPERN, B., CARTER, L., FEIG, E., AND SELKER, T. 1994. The uniform memory hierarchy model of computation. Algorithmica 12, 2-3, 72-109.
• 19: Lars Arge, The Buffer Tree: A New Technique for Optimal I/O-Algorithms (Extended Abstract), Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.334-345, August 16-18, 1995
• 20: Lars Arge, The I/O - Complexity of Ordered Binary - Decision Diagram Manipulation, Proceedings of the 6th International Symposium on Algorithms and Computation, p.82-91, December 04-06, 1995
• 21: Lars Arge, External-Memory Algorithms with Applications in GIS, Algorithmic Foundations of Geographic Information Systems, this book originated from the CISM Advanced School on the Algorithmic Foundations of Geographic Information Systems, p.213-254, September 16-20, 1996
• 22: Lars Arge , Peter Bro Miltersen, On showing lower bounds for external-memory computational geometry problems, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 23: Lars Arge , Jan Vahrenhold, I/O-efficient dynamic planar point location (extended abstract), Proceedings of the sixteenth annual symposium on Computational geometry, p.191-200, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336205]
• 24: L. Arge , J. S. Vitter, Optimal dynamic interval management in external memory, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.560, October 14-16, 1996
• 25: Lars Arge , Gerth Stølting Brodal , Laura Toma, On External-Memory MST, SSSP, and Multi-way Planar Graph Separation, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.433-447, July 05-07, 2000
• 26: Lars Arge , Paolo Ferragina , Roberto Grossi , Jeffrey Scott Vitter, On sorting strings in external memory (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.540-548, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258647]
• 27: Lars Arge , Klaus Hinrichs , Jan Vahrenhold , Jeffrey Scott Vitter, Efficient Bulk Operations on Dynamic R-trees, Selected papers from the International Workshop on Algorithm Engineering and Experimentation, p.328-348, January 15-16, 1999
• 28: Lars Arge , Mikael Knudsen , Kirsten Larsen, A General Lower Bound on the I/O-Complexity of Comparison-based Algorithms, Proceedings of the Third Workshop on Algorithms and Data Structures, p.83-94, August 11-13, 1993
• 29: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jan Vahrenhold , Jeffrey Scott Vitter, A Unified Approach for Indexed and Non-Indexed Spatial Joins, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.413-429, March 27-31, 2000
• 30: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter, Scalable Sweeping-Based Spatial Join, Proceedings of the 24rd International Conference on Very Large Data Bases, p.570-581, August 24-27, 1998
• 31: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter, Theory and practice of I/O-efficient algorithms for multidimensional batched searching problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.685-694, January 25-27, 1998, San Francisco, California, United States
• 32: Lars Arge , Vasilis Samoladas , Jeffrey Scott Vitter, On two-dimensional indexability and optimal range search indexing, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.346-357, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304010]
• 33: Lars Arge , Darren Erik Vengroff , Jeffrey Scott Vitter, External-Memory Algorithms for Processing Line Segments in Geographic Information Systems (Extended Abstract), Proceedings of the Third Annual European Symposium on Algorithms, p.295-310, September 25-27, 1995
• 34: Chris Armen, Bounds on the separation of two parallel disk models, Proceedings of the fourth workshop on I/O in parallel and distributed systems: part of the federated computing research conference, p.122-127, May 27-27, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/236017.236044]
• 35: Ricardo A. Baeza-Yates, Bounded disorder: the effect of the index, Theoretical Computer Science, v.168 n.1, p.21-38, Nov. 10, 1996
• 36: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 37: Ricardo A. Baeza-Yates , Héctor Soza-Pollman, Analysis of linear hashing revisited, Nordic Journal of Computing, v.5 n.1, p.70-85, Spring 1998
• 38: Ricardo A. Baeza-Yates, Expected behaviour of B+-trees under random insertions, Acta Informatica, v.26 n.5, p.439-471, 1989 [doi>10.1007/BF00289146]
• 39: R. A. Baeza-Yates , P. -A. Larson, Performance of B±Trees with Partial Expansions, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.248-257, June 1989 [doi>10.1109/69.87964]
• 40: Rakesh D. Barve , Jeffrey Scott Vitter, A simple and efficient parallel disk mergesort, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.232-241, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305646]
• 41: Rakesh D. Barve , Jeffrey Scott Vitter, A Theoretical Framework for Memory-Adaptive Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.273, October 17-18, 1999
• 42: Rakesh D. Barve , Edward F. Grove , Jeffrey Scott Vitter, Simple randomized mergesort on parallel disks, Parallel Computing, v.23 n.4-5, p.601-631, June 1, 1997 [doi>10.1016/S0167-8191(97)00015-X]
• 43: Rakesh Barve , Mahesh Kallahalla , Peter J. Varman , Jeffrey Scott Vitter, Competitive parallel disk prefetching and buffer management, Journal of Algorithms, v.36 n.2, p.152-181, Aug. 2000 [doi>10.1006/jagm.2000.1089]
• 44: Rakesh Barve , Elizabeth Shriver , Phillip B. Gibbons , Bruce K. Hillyer , Yossi Matias , Jeffrey Scott Vitter, Modeling and optimizing I/O throughput of multiple disks on a bus, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.83-92, May 01-04, 1999, Atlanta, Georgia, United States
• 45: Julien Basch , Leonidas J. Guibas, Data structures for mobile data, Journal of Algorithms, v.31 n.1, p.1-28, April 1999 [doi>10.1006/jagm.1998.0988]
• 46: BAYER,R.AND MCCREIGHT, E. 1972. Organization of large ordered indexes. Acta Informatica 1, 173- 189.
• 47: Rudolf Bayer , Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977 [doi>10.1145/320521.320530]
• 48: Bruno Becker , Stephan Gschwind , Thomas Ohler , Bernhard Seeger , Peter Widmayer, An asymptotically optimal multiversion B-tree, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.264-275, December 1996 [doi>10.1007/s007780050028]
• 49: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 50: M. A. Bender , E. D. Demaine , M. Farach-Colton, Cache-oblivious B-trees, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.399, November 12-14, 2000
• 51: Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
• 52: BENTLEY,J.L.AND SAXE, J. B. 1980. Decomposable searching problems I: Static-to-dynamic transformations. Journal of Algorithms 1, 4 (Dec.), 301-358.
• 53: Stefan Berchtold , Christian Böhm , Hans-Peter Kriegel, Improving the Query Performance of High-Dimensional Index Structures by Bulk-Load Operations, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.216-230, March 23-27, 1998
• 54: BLUM,N.AND MEHLHORN, K. 1980. On the average number of rebalancing operations in weightbalanced trees. Theoretical Computer Science 11, 3 (July), 303-320.
• 55: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 56: Klaus Brengel , Andreas Crauser , Paolo Ferragina , Ulrich Meyer, An Experimental Study of Priority Queues in External Memory, Proceedings of the 3rd International Workshop on Algorithm Engineering, p.345-359, July 19-21, 1999
• 57: Gerth Stølting Brodal , Jyrki Katajainen, Worst-Case External-Memory Priority Queues, Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, p.107-118, July 08-10, 1998
• 58: Adam L. Buchsbaum , Michael Goldwasser , Suresh Venkatasubramanian , Jeffery R. Westbrook, On external memory graph traversal, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.859-860, January 09-11, 2000, San Francisco, California, United States
• 59: Paul B. Callahan , Michael T. Goodrich , Kumar Ramaiyer, Topology B-Trees and Their Applications, Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.381-392, August 16-18, 1995
• 60: Larry Carter , Kang Su Gatlin, Towards an Optimal Bit-Reversal Permutation Program, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.544, November 08-11, 1998
• 61: Bernard Chazelle, Filtering search: a new approach to query answering, SIAM Journal on Computing, v.15 n.3, p.703-724, August 1986 [doi>10.1137/0215051]
• 62: Bernard Chazelle, Lower bounds for orthogonal range searching: I. The reporting case, Journal of the ACM (JACM), v.37 n.2, p.200-212, April 1990 [doi>10.1145/77600.77614]
• 63: CHAZELLE,B.AND EDELSBRUNNER, H. 1987. Linear space data structures for two types of range search. Discrete and Computational Geometry 2, 113-126.
• 64: Peter M. Chen , Edward K. Lee , Garth A. Gibson , Randy H. Katz , David A. Patterson, RAID: high-performance, reliable secondary storage, ACM Computing Surveys (CSUR), v.26 n.2, p.145-185, June 1994 [doi>10.1145/176979.176981]
• 65: Yi-Jen Chiang, Experiments on the practical I/O efficiency of geometric algorithms: distribution sweep versus plane sweep, Computational Geometry: Theory and Applications, v.9 n.4, p.211-236, March 1998 [doi>10.1016/S0925-7721(97)00020-5]
• 66: Yi-Jen Chiang , Michael T. Goodrich , Edward F. Grove , Roberto Tamassia , Darren Erik Vengroff , Jeffrey Scott Vitter, External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.139-149, January 22-24, 1995, San Francisco, California, United States
• 67: Yi-Jen Chiang , Cláudio T. Silva, External memory techniques for isosurface extraction in scientific visualization, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 68: David R. Clark , J. Ian Munro, Efficient suffix trees on secondary storage, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.383-391, January 28-30, 1996, Atlanta, Georgia, United States
• 69: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 70: A. Colvin , T. Cormen, ViC*: A Compiler for Virtual-Memory C*, Proceedings of the High-Level Parallel Programming Models and Supportive Environments, p.23, March 30-April 03, 1998
• 71: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 72: CORBETT, P., FEITELSON, D., FINEBERG, S., HSU,Y., NITZBERG, B., PROST, J.-P., SNIR, M., TRAVERSAT, B., AND WONG, P. 1996. Overview of the MPI- IO parallel I/O interface. In R., Jain, J., Werth, and J. C. Browne, Eds., Input/Output in Parallel and Distributed Computer Systems, Vol. 362 of The Kluwer International Series in Engineering and Computer Science, Kluwer Academic, Chapter 5, 127-146.
• 73: Peter F. Corbett , Dror G. Feitelson, The Vesta parallel file system, ACM Transactions on Computer Systems (TOCS), v.14 n.3, p.225-264, Aug. 1996 [doi>10.1145/233557.233558]
• 74: Thomas H. Cormen , David M. Nicol, Performing out-of-core FFTs on parallel disk systems, Parallel Computing, v.24 n.1, p.5-20, Jan. 1998 [doi>10.1016/S0167-8191(97)00114-2]
• 75: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 76: Thomas H. Cormen , Thomas Sundquist , Leonard F. Wisniewski, Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems, SIAM Journal on Computing, v.28 n.1, p.105-136, Feb. 1999 [doi>10.1137/S0097539795283681]
• 77: Andreas Crauser , Paolo Ferragina, On Constructing Suffix Arrays in External Memory, Proceedings of the 7th Annual European Symposium on Algorithms, p.224-235, July 16-18, 1999
• 78: Andreas Crauser , Kurt Mehlhorn, LEDA-SM Extending LEDA to Secondary Memory, Proceedings of the 3rd International Workshop on Algorithm Engineering, p.228-242, July 19-21, 1999
• 79: A. Crauser , P. Ferragina , K. Mehlhorn , U. Meyer , E. Ramos, Randomized external-memory algorithms for some geometric problems, Proceedings of the fourteenth annual symposium on Computational geometry, p.259-268, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276914]
• 80: A. Crauser , P. Ferragina , K. Mehlhorn , U. Meyer , E. A. Ramos, I/O-optimal computation of segment intersections, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 81: Robert Cypher , C. Greg Plaxton, Deterministic sorting in nearly logarithmic time on the hypercube and related computers, Journal of Computer and System Sciences, v.47 n.3, p.501-548, Dec. 1993 [doi>10.1016/0022-0000(93)90043-V]
• 82: Mark de Berg , Joachim Gudmundsson , Mikael Hammar , Mark H. Overmars, On R-trees with Low Stabbing Number, Proceedings of the 8th Annual European Symposium on Algorithms, p.167-178, September 05-08, 2000
• 83: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 84: Frank Dehne , Wolfgang Dittrich , David Hutchinson, Efficient external memory algorithms by simulating coarse-grained parallel algorithms, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.106-115, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258503]
• 85: Frank K. H. A. Dehne , David Hutchinson , Anil Maheshwari , Wolfgang Dittrich, Reducing I/O Complexity by Simulating Coarse Grained Parallel Algorithms, Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, p.14-20, April 12-16, 1999
• 86: DEMUTH, H. B. 1956. Electronic data sorting. Ph.D., Stanford University. A shortened version appears in IEEE Transactions on Computing C-34, 4, (April), 296-310, 1985, Special Issue on Sorting, E. E. Lindstrom, C. K. Wong, and J. S. Vitter, Eds.
• 87: DENNING, P. J. 1980. Working sets past and present. IEEE Transactions on Software Engineering SE-6, 64-84.
• 88: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider, Parallel sorting on a shared-nothing architecture using probabilistic splitting, Proceedings of the first international conference on Parallel and distributed information systems, p.280-291, December 1991, Miami, Florida, United States
• 89: Wolfgang Dittrich , David Hutchinson , Anil Maheshwari, Blocking in parallel multisearch problems (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.98-107, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277676]
• 90: James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
• 91: Malcolm C Easton, Key-sequence data sets on indelible storage, IBM Journal of Research and Development, v.30 n.3, p.230-241, May 1986
• 92: EDELSBRUNNER, H. 1983a. A new approach to rectangle intersections, part I. International Journal of Computer Mathematics 13, 209-219.
• 93: EDELSBRUNNER, H. 1983b. A new approach to rectangle intersections, part II. International Journal of Computer Mathematics 13, 221-229.
• 94: R. J. Enbody , H. C. Du, Dynamic hashing schemes, ACM Computing Surveys (CSUR), v.20 n.2, p.850-113, June 1988 [doi>10.1145/46157.330532]
• 95: David Eppstein , Zvi Galil , Giuseppe F. Italiano , Amnon Nissenzweig, Sparsification—a technique for speeding up dynamic graph algorithms, Journal of the ACM (JACM), v.44 n.5, p.669-696, Sept. 1997 [doi>10.1145/265910.265914]
• 96: Georgios Evangelidis , David Lomet , Betty Salzberg, The hB $^\Pi$-tree: a multi-attribute index supporting concurrency, recovery and node consolidation, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.1, p.1-25, February 1997 [doi>10.1007/s007780050030]
• 97: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• 98: Martin Farach , Paolo Ferragina , S. Muthukrishnan, Overcoming the Memory Bottleneck in Suffix Tree Construction, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.174, November 08-11, 1998
• 99: J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, An Approximate L1-Difference Algorithm for Massive Data Streams, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.501, October 17-18, 1999
• 100: FELLER, W. 1968. An Introduction to Probability Theory and its Applications, Vol. 1, 3rd edition. John Wiley, New York.
• 101: Paolo Ferragina , Roberto Grossi, Fast string searching in secondary storage: theoretical developments and experimental results, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.373-382, January 28-30, 1996, Atlanta, Georgia, United States
• 102: Paolo Ferragina , Roberto Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM (JACM), v.46 n.2, p.236-280, March 1999 [doi>10.1145/301970.301973]
• 103: Paolo Ferragina , Fabrizio Luccio, Dynamic dictionary matching in external memory, Information and Computation, v.146 n.2, p.85-99, Nov. 1, 1998 [doi>10.1006/inco.1998.2733]
• 104: FLAJOLET, P. 1983. On the performance evaluation of extendible hashing and trie searching. Acta Informatica 20, 4, 345-369.
• 105: FLOYD, R. W. 1972. Permuting information in idealized two-level storage. In R. Miller and J. Thatcher, Eds., Complexity of Computer Computations. Plenum, New York, 105-109.
• 106: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 107: Matteo Frigo , Charles E. Leiserson , Harald Prokop , Sridhar Ramachandran, Cache-Oblivious Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.285, October 17-18, 1999
• 108: Thomas A. Funkhouser , Carlo H. Séquin , Seth J. Teller, Management of large amounts of data in interactive building walkthroughs, Proceedings of the 1992 symposium on Interactive 3D graphics, p.11-20, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147158]
• 109: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 110: GANGER, G. R. 1995. Generating representative synthetic workloads: An unsolved problem. In Proceedings of the Computer Measurement Group Conference (Dec.), Vol. 21, 1263-1269.
• 111: GARDNER, M. 1977. Magic Show. Knopf, New York, Chapter 7.
• 112: Irene Gargantini, An effective way to represent quadtrees, Communications of the ACM, v.25 n.12, p.905-910, Dec 1982 [doi>10.1145/358728.358741]
• 113: Garth A. Gibson , Jeffrey Scott Vitter , John Wilkes, Strategic directions in storage I/O issues in large-scale computing, ACM Computing Surveys (CSUR), v.28 n.4, p.779-793, Dec. 1996 [doi>10.1145/242223.242300]
• 114: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 115: Roy Goldman , Narayanan Shivakumar , Suresh Venkatasubramanian , Hector Garcia-Molina, Proximity Search in Databases, Proceedings of the 24rd International Conference on Very Large Data Bases, p.26-37, August 24-27, 1998
• 116: GOODRICH,M.T.,TSAY, J.-J., VENGROFF,D.E.,AND VITTER, J. S. 1993. External-memory computational geometry. In Proceedings of the IEEE Symposium on Foundations of Computer Science Palo Alto (Nov.), Vol. 34, 714-723.
• 117: Satish Govindarajan , Tamás Lukovszki , Anil Maheshwari , Norbert Zeh, I/O-Efficient Well-Separated Pair Decomposition and Its Applications, Proceedings of the 8th Annual European Symposium on Algorithms, p.220-231, September 05-08, 2000
• 118: Diane Greene, An Implementation and Performance Analysis of Spatial Data Access Methods, Proceedings of the Fifth International Conference on Data Engineering, p.606-615, February 06-10, 1989
• 119: John Linwood Griffin , Steven W. Schlosser , Gregory R. Ganger , David F. Nagle, Modeling and performance of MEMS-based storage devices, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.56-65, June 18-21, 2000, Santa Clara, California, United States
• 120: Roberto Grossi , Giuseppe F. Italiano, Efficient cross-trees for external memory, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 121: Roberto Grossi , Giuseppe F. Italiano, Efficient Splitting and Merging Algorithms for Order Decomposable Problems (Extended Abstract), Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.605-615, July 07-11, 1997
• 122: GUPTA,S.K.S.,LI, Z., AND REIF, J. H. 1995. Generating efficient programs for two-level memories from tensor-products. In Proceedings of the IASTED/ISMM International Conference on Parallel and Distributed Computing and Systems (Washington, DC, Oct.), Vol. 7, 510- 513.
• 123: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 124: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 125: Joseph M. Hellerstein , Elias Koutsoupias , Christos H. Papadimitriou, On the analysis of indexing schemes, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.249-256, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263688]
• 126: HELLERSTEIN, L., GIBSON, G., KARP, R. M., KATZ,R.H., AND PATTERSON, D. A. 1994. Coding techniques for handling failures in large disk arrays. Algorithmica 12, 2-3, 182-208.
• 127: Monika R. Henzinger , Prabhakar Raghavan , Sridhar Rajagopalan, Computing on data streams, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 128: HINRICHS, K. H. 1985. The grid file system: Implementation and case studies of applications. PhD Thesis, Dept. Information Science, ETH, Zurich.
• 129: Hong Jia-Wei , H. T. Kung, I/O complexity: The red-blue pebble game, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.326-333, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802486]
• 130: HUTCHINSON, D., MAHESHWARI, A., SACK, J.-R., AND VELICESCU, R. 1997. Early experiences in implementing the buffer tree. In Proceedings of the Workshop on Algorithm Engineering, Vol. 1.
• 131: HUTCHINSON, D., MAHESHWARI, A., AND ZEH, N. 1999. An external memory data structure for shortest path queries. In Proceedings of the International Conference on Computing and Combinatorics (July), Vol. 1627 of Lecture Notes in Computer Science, Springer-Verlag, 51-60.
• 132: David A. Hutchinson , Peter Sanders , Jeffrey Scott Vitter, Duality between Prefetching and Queued Writing with Parallel Disks, Proceedings of the 9th Annual European Symposium on Algorithms, p.62-73, August 28-31, 2001
• 133: David A. Hutchinson , Peter Sanders , Jeffrey Scott Vitter, The power of duality for prefetching and sorting with parallel disks, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.334-335, July 2001, Crete Island, Greece [doi>10.1145/378580.378760]
• 134: HUTCHINSON, D. A., SANDERS,P.,AND VITTER,J.S. 2001c. Notes.
• 135: Piotr Indyk , Rajeev Motwani , Prabhakar Raghavan , Santosh Vempala, Locality-preserving hashing in multidimensional spaces, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.618-625, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258656]
• 136: Dieter Pfoser , Christian S. Jensen , Yannis Theodoridis, Novel Approaches in Query Processing for Moving Object Trajectories, Proceedings of the 26th International Conference on Very Large Data Bases, p.395-406, September 10-14, 2000
• 137: Mahesh Kallahalla , Peter J. Varman, Optimal read-once parallel disk scheduling, Proceedings of the sixth workshop on I/O in parallel and distributed systems, p.68-77, May 05-05, 1999, Atlanta, Georgia, United States [doi>10.1145/301816.301835]
• 138: Mahesh Kallahalla , Peter J. Varman, Optimal prefetching and caching for parallel I/O sytems, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.219-228, July 2001, Crete Island, Greece [doi>10.1145/378580.378648]
• 139: Ibrahim Kamel , Christos Faloutsos, On packing R-trees, Proceedings of the second international conference on Information and knowledge management, p.490-499, November 01-05, 1993, Washington, D.C., United States [doi>10.1145/170088.170403]
• 140: Ibrahim Kamel , Christos Faloutsos, Hilbert R-tree: An Improved R-tree using Fractals, Proceedings of the 20th International Conference on Very Large Data Bases, p.500-509, September 12-15, 1994
• 141: KAMEL, I., KHALIL, M., AND KOURAMAJIAN, V. 1996. Bulk insertion in dynamic R-trees. In Proceedings of the International Symposium on Spatial Data Handling, Vol. 4, 3B, 31-42.
• 142: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.299-313, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298582]
• 143: Paris Kanellakis , Sridhar Ramaswamy , Darren E. Vengroff , Jeffrey Scott Vitter, Indexing for data models with constraints and classes, Journal of Computer and System Sciences, v.52 n.3, p.589-612, June 1996 [doi>10.1006/jcss.1996.0043]
• 144: Kothuri Venkata Ravi Kanth , Ambuj K. Singh, Optimal Dynamic Range Searching in Non-replicating Index Structures, Proceeding of the 7th International Conference on Database Theory, p.257-276, January 10-12, 1999
• 145: M Y Kim, Synchronized disk interleaving, IEEE Transactions on Computers, v.35 n.11, p.978-988, Nov. 1986 [doi>10.1109/TC.1986.1676699]
• 146: David G Kirkpatrick , Raimund Seidel, The ultimate planar convex hull algorithm, SIAM Journal on Computing, v.15 n.1, p.287-299, Feb. 1986 [doi>10.1137/0215021]
• 147: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 148: KNUTH, D. E. 1999. MMIXware. Springer, Berlin.
• 149: KNUTH, D. E., MORRIS,J.H.,AND PRATT, V. R. 1977. Fast pattern matching in strings. SIAM Journal on Computing 6, 323-350.
• 150: George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, On indexing mobile objects, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.261-272, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304002]
• 151: Elias Koutsoupias , D. S. Taylor, Tight bounds for 2-dimensional indexing schemes, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.52-58, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275494]
• 152: KRISHNAMURTHY,R.AND WANG, K.-Y. 1985. Multilevel grid files. Technical Report, IBM T. J. Watson Center, Yorktown Heights, NY, November.
• 153: Vijay Kumar , Eric J. Schwabe, Improved Algorithms and Data Structures for Solving Graph Problems in External Memory, Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP '96), p.169, October 23-26, 1996
• 154: KUSPERT, K. 1983. Storage utilization in B*-trees with a generalized overflow technique. Acta Informatica, 19, 35-55.
• 155: Per-Åke Larson, Performance analysis of linear hashing with partial expansions, ACM Transactions on Database Systems (TODS), v.7 n.4, p.566-587, Dec. 1982 [doi>10.1145/319758.319763]
• 156: LAURINI,R.AND THOMPSON, D. 1992. Fundamentals of Spatial Information Systems. Academic Press.
• 157: Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981 [doi>10.1145/319628.319663]
• 158: Tom Leighton, Tight bounds on the complexity of parallel sorting, IEEE Transactions on Computers, v.34 n.4, p.344-354, April 1985 [doi>10.1109/TC.1985.5009385]
• 159: LEISERSON, C. E., RAO,S.,AND TOLEDO, S. 1993. Efficient out-of-core algorithms for linear relaxation using blocking covers. In Proceedings of the IEEE Symposium on Foundations of Computer Science, Vol. 34, 704-713.
• 160: LI, Z., MILLS,P.H.,AND REIF, J. H. 1996. Models and resource metrics for parallel and distributed computation. Parallel Algorithms and Applications 8, 35-59.
• 161: LITWIN, W. 1980. Linear hashing: A new tool for files and tables addressing. In Proceedings of the International Conference on Very Large Databases (Montreal, Oct.), Vol. 6, 212-223.
• 162: LITWIN,W.AND LOMET, D. 1987. A new method for fast data searches with keys. IEEE Software 4, 2 (March), 16-24.
• 163: David B. Lomet, A simple bounded disorder file organization with good performance, ACM Transactions on Database Systems (TODS), v.13 n.4, p.525-551, Dec. 1988 [doi>10.1145/49346.50067]
• 164: David B. Lomet , Betty Salzberg, The hB-tree: a multiattribute indexing method with good guaranteed performance, ACM Transactions on Database Systems (TODS), v.15 n.4, p.625-658, Dec. 1990 [doi>10.1145/99935.99949]
• 165: David Lomet , Betty Salzberg, Concurrency and recovery for index trees, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.3, p.224-240, August 1997 [doi>10.1007/s007780050042]
• 166: MAHESHWARI,A.AND ZEH, N. External memory algorithms for outerplanar graphs. In Proceedings of the International Conference on Computing and Combinatorics (July), Vol. 1627 of Lecture Notes in Computer Science, Springer-Verlag, 51-60.
• 167: Anil Maheshwari , Norbert Zeh, I/O-efficient algorithms for graphs of bounded treewidth, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.89-90, January 07-09, 2001, Washington, D.C., United States
• 168: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing, v.22 n.5, p.935-948, Oct. 1993 [doi>10.1137/0222058]
• 169: MANBER,U.AND WU, S. 1994. GLIMPSE: A tool to search through entire file systems. In USENIX Association, Ed., Proceedings of the Winter USENIX Conference (San Francisco, Jan.), 23- 32.
• 170: G. N.N. Martin, Spiral Storage: Incrementally Augmentable Hash Addressed Storage, University of Warwick, Coventry, UK, 1979
• 171: Yossi Matias , Eran Segal , Jeffrey Scott Vitter, Efficient bundle sorting, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.839-848, January 09-11, 2000, San Francisco, California, United States
• 172: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 173: MCCREIGHT, E. M. 1985. Priority search trees. SIAM Journal on Computing 14, 2 (May), 257- 276.
• 174: MENDELSON, H. 1982. Analysis of extendible hashing. IEEE Transactions on Software Engineering SE-8 (Nov.), 611-619.
• 175: Ulrich Meyer, External memory BFS on undirected graphs with bounded degree, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.87-88, January 07-09, 2001, Washington, D.C., United States
• 176: Microsoft 1998. TerraServer online database of satellite images, available on the World-Wide Web at http://terraserver.microsoft.com/.
• 177: C. Mohan, ARIES/KVL: a key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes, Proceedings of the sixteenth international conference on Very large databases, p.392-405, September 1990, Brisbane, Australia
• 178: Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM (JACM), v.15 n.4, p.514-534, Oct. 1968 [doi>10.1145/321479.321481]
• 179: Steven A. Moyer , V. S. Sunderam, Characterizing concurrency control performance for the PIOUS parallel file system, Journal of Parallel and Distributed Computing, v.38 n.1, p.81-91, Oct. 10, 1996 [doi>10.1006/jpdc.1996.0130]
• 180: MULLIN, J. K. 1985. Spiral storage: Efficient dynamic hashing with constant performance. The Computer Journal 28, 3 (July), 330-334.
• 181: Kameshwar Munagala , Abhiram Ranade, I/O-complexity of graph algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.687-694, January 17-19, 1999, Baltimore, Maryland, United States
• 182: NASA 1999. Earth Observing System (EOS) web page, NASA Goddard Space Flight Center, http://eospso.gsfc.nasa.gov/.
• 183: NIEVERGELT,J.AND REINGOLD, E. M. 1973. Binary search tree of bounded balance. SIAM Journal on Computing 2,1.
• 184: Jürg Nievergelt , Peter Widmayer, Spatial Data Structures: Concepts and Design Choices, Algorithmic Foundations of Geographic Information Systems, this book originated from the CISM Advanced School on the Algorithmic Foundations of Geographic Information Systems, p.153-197, September 16-20, 1996
• 185: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 186: Mark H. Nodine , Jeffrey Scott Vitter, Deterministic distribution sort in shared and distributed memory multiprocessors, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.120-129, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165247]
• 187: Mark H. Nodine , Jeffrey Scott Vitter, Greed sort: optimal deterministic sorting on parallel disks, Journal of the ACM (JACM), v.42 n.4, p.919-933, July 1995 [doi>10.1145/210332.210343]
• 188: NODINE, M. H., GOODRICH,M.T.,AND VITTER,J.S. 1996. Blocking for external graph searching. Algorithmica 16, 2 (August), 181-214.
• 189: Mark H. Nodine , Daniel P. Lopresti , Jeffrey S. Vitter, I/O Overhead and Parallel VLSI Architectures for Lattice Computations, IEEE Transactions on Computers, v.40 n.7, p.843-852, July 1991 [doi>10.1109/12.83622]
• 190: Patrick E. O'Neil, The SB-tree: an index-sequential structure for high-performance sequential access, Acta Informatica, v.29 n.3, p.241-265, June 1992 [doi>10.1007/BF01185680]
• 191: J. A. Orenstein, Redundancy in spatial databases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.295-305, June 1989, Portland, Oregon, United States
• 192: J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588037]
• 193: Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 194: HweeHwa Pang , Michael J. Carey , Miron Livny, Memory-Adaptive External Sorting, Proceedings of the 19th International Conference on Very Large Data Bases, p.618-629, August 24-27, 1993
• 195: Hwee Hwa Pang , Michael J. Carey , Miron Livny, Partially preemptible hash joins, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.59-68, May 25-28, 1993, Washington, D.C., United States
• 196: Ian Parsons , Ron Unrau , Jonathan Schaeffer , Duane Szafron, PI/OT: parallel I/O templates, Parallel Computing, v.23 n.4-5, p.543-570, June 1, 1997 [doi>10.1016/S0167-8191(97)00013-6]
• 197: Jignesh M. Patel , David J. DeWitt, Partition based spatial-merge join, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.259-270, June 04-06, 1996, Montreal, Quebec, Canada
• 198: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 199: RAHMAN,N.,AND RAMAN, R. 2000. Adapting radix sort to the memory hierarchy. In Workshop on Algorithm Engineering and Experimentation (Jan.), Vol. 1982 of Lecture Notes in Computer Science. Springer-Verlag.
• 200: Sridhar Ramaswamy , Sairam Subramanian, Path caching (extended abstract): a technique for optimal external searching, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.25-35, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182595]
• 201: Jun Rao , Kenneth A. Ross, Cache Conscious Indexing for Decision-Support in Main Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.78-89, September 07-10, 1999
• 202: Jun Rao , Kenneth A. Ross, Making B+- trees cache conscious in main memory, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.475-486, May 15-18, 2000, Dallas, Texas, United States
• 203: Erik Riedel , Garth A. Gibson , Christos Faloutsos, Active Storage for Large-Scale Data Mining and Multimedia, Proceedings of the 24rd International Conference on Very Large Data Bases, p.62-73, August 24-27, 1998
• 204: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 205: Mendel Rosenblum , Edouard Bugnion , Scott Devine , Stephen A. Herrod, Using the SimOS machine simulator to study complex computer systems, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.1, p.78-103, Jan. 1997 [doi>10.1145/244804.244807]
• 206: Chris Ruemmler , John Wilkes, An introduction to disk drive modeling, Computer, v.27 n.3, p.17-28, March 1994 [doi>10.1109/2.268881]
• 207: Kenneth Salem , Hector Garcia-Molina, Disk Striping, Proceedings of the Second International Conference on Data Engineering, p.336-342, February 05-07, 1986
• 208: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 209: Betty Salzberg , Vassilis J. Tsotras, Comparison of access methods for time-evolving data, ACM Computing Surveys (CSUR), v.31 n.2, p.158-221, June 1999 [doi>10.1145/319806.319816]
• 210: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 211: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 212: Vasilis Samoladas , Daniel P. Miranker, A lower bound theorem for indexing schemes and its application to multidimensional range queries, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.44-51, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275493]
• 213: Peter Sanders, Fast Priority Queues for Cached Memory, Selected papers from the International Workshop on Algorithm Engineering and Experimentation, p.312-327, January 15-16, 1999
• 214: SANDERS, P. 2000. Personal communication.
• 215: Peter Sanders, Reconciling simplicity and realism in parallel disk models, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.67-76, January 07-09, 2001, Washington, D.C., United States
• 216: Peter Sanders , Sebastian Egner , Jan Korst, Fast concurrent access to parallel disks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.849-858, January 09-11, 2000, San Francisco, California, United States
• 217: John E. Savage, Extending the Hong-Kung Model to Memory Hierarchies, Proceedings of the First Annual International Conference on Computing and Combinatorics, p.270-281, August 24-26, 1995
• 218: SAVAGE,J.E.AND Vitter, J. S. 1987. Parallelism in space-time tradeoffs. In F. P. Preparata, Ed., Advances in Computing Research, Vol. 4, JAI Press, Grreenwich, CT, 117-146.
• 219: Steven W. Schlosser , John Linwood Griffin , David F. Nagle , Gregory R. Ganger, Designing computer systems with MEMS-based storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.1-12, November 2000, Cambridge, Massachusetts, United States
• 220: Kent E. Seamons , Marianne Winslett, Multidimensional array I/O in Panda 1.0, The Journal of Supercomputing, v.10 n.2, p.191-211, June 1996
• 221: Bernhard Seeger , Hans-Peter Kriegel, The buddy tree: an efficient and robust access method for spatial data base, Proceedings of the sixteenth international conference on Very large databases, p.590-601, September 1990, Brisbane, Australia
• 222: SELTZER, M., SMITH, K. A., BALAKRISHNAN, H., CHANG, J., MCMAINS,S.,AND PADMANABHAN, V. 1995. File system logging versus clustering: A performance comparison. In Proceedings of the Annual USENIX Technical Conference (New Orleans), 249-264.
• 223: Sandeep Sen , Siddhartha Chatterjee, Towards a theory of cache-efficient algorithms, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.829-838, January 09-11, 2000, San Francisco, California, United States
• 224: Elizabeth Shriver , Arif Merchant , John Wilkes, An analytic behavior model for disk drives with readahead caches and request reordering, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.182-191, June 22-26, 1998, Madison, Wisconsin, United States
• 225: SHRIVER,E.A.M.AND NODINE, M. H. 1996. An introduction to parallel I/O models and algorithms. In R. Jain, J. Werth, and J. C. Browne, Eds. Input/Output in Parallel and Distributed Computer Systems, Kluwer Academic, Chapter 2, 31-68.
• 226: Elizabeth A. M. Shriver , Leonard F. Wisniewski, An API for Choreographing Data Accesses, Dartmouth College, Hanover, NH, 1995
• 227: SIBEYN, J. F. 1997. From parallel to external list ranking. Technical Report MPI-I-97-1-021, Max-Planck-Institut, September.
• 228: SIBEYN, J. F. 1999. External selection. In Proceedings of the Symposium on Theoretical Aspects of Computer Science, Vol. 1563 of Lecture Notes in Computer Science, Springer-Verlag, 291-301.
• 229: Jop F. Sibeyn , Michael Kaufmann, BSP-Like External-Memory Computation, Proceedings of the Third Italian Conference on Algorithms and Complexity, p.229-240, March 12-14, 1997
• 230: B. Srinivasan, An adaptive overflow technique to defer splitting in B-trees, The Computer Journal, v.34 n.5, p.397-405, Oct. 1991 [doi>10.1093/comjnl/34.5.397]
• 231: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, ACM SIGPLAN Notices, v.29 n.6, p.196-205, June 1994
• 232: Sairam Subramanian , Sridhar Ramaswamy, The P-range tree: a new data structure for range searching in secondary memory, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.378-387, January 22-24, 1995, San Francisco, California, United States
• 233: TAMASSIA,R.AND VITTER, J. S. 1996. Optimal cooperative search in fractional cascaded data structures. Algorithmica 15, 2 (Feb.), 154-171.
• 234: Rajeev Thakur , Alok Choudhary , Rajesh Bordawekar , Sachin More , Sivaramakrishna Kuditipudi, Passion: Optimized I/O for Parallel Applications, Computer, v.29 n.6, p.70-78, June 1996
• 235: TIGER/Line (tm). 1992. Technical documentation. Technical Report, USBureau of the Census.
• 236: Sivan Toledo, A survey of out-of-core algorithms in numerical linear algebra, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 237: TPIE. 1999. User manual and reference, The manual and software distribution are available on the web at http://www.cs.duke.edu/TPIE/.
• 238: ULLMAN,J.D.AND YANNAKAKIS, M. 1991. The input/output complexity of transitive closure. Annals of Mathematics and Artificial Intelligence 3, 331-360.
• 239: Jochen Van den Bercken , Bernhard Seeger , Peter Widmayer, A Generic Approach to Bulk Loading Multidimensional Index Structures, Proceedings of the 23rd International Conference on Very Large Data Bases, p.406-415, August 25-29, 1997
• 240: VAN KREVELD, M., NIEVERGELT, J., ROOS, T., AND WINDMAYER, P. Eds. 1997. Algorithmic Foundations of GIS, Vol. 1340 of Lecture Notes in Computer Science, Springer-Verlag.
• 241: Peter J. Varman , Rakesh M. Verma, An Efficient Multiversion Access Structure, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.391-409, May 1997 [doi>10.1109/69.599929]
• 242: Darren Erik Vengroff , Jeffrey Scott Vitter, Efficient 3-D range searching in external memory, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.192-201, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237864]
• 243: VENGROFF,D.E.AND VITTER, J. S. 1996b. I/O- efficient scientific computation using TPIE. In Proceedings of NASA Goddard Conference on Mass Storage Systems (Sept.), Vol. 5, II, 553- 570.
• 244: VETTIGER, P., DESPONT, M., DRECHSLER, U., DURIG,U., HABERLE, W., LUTWYCHE, M. I., ROTHUIZEN, E., STUTZ, R., WIDMER, R., AND BINNIG, G. K. 2000. The "Millipede"-More than one thousand tips for future AFM data storage. IBM Journal of Research and Development 44, 3, 323-340.
• 245: Jeffrey Scott Vitter, Efficient memory access in large-scale computation (invited paper), Proceedings of the 8th annual symposium on Theoretical aspects of computer science, p.26-41, February 1991, Hamburg, Germany
• 246: Jeffrey Scott Vitter, External Memory Algorithms, Proceedings of the 6th Annual European Symposium on Algorithms, p.1-25, August 24-26, 1998
• 247: Jeffrey Scott Vitter, External memory algorithms and data structures, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 248: Jeffrey Scott Vitter, Online Data Structures in External Memory, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.119-133, July 11-15, 1999
• 249: Jeffrey Scott Vitter, Online Data Structures in External Memory, Proceedings of the 6th International Workshop on Algorithms and Data Structures, p.352-366, August 11-14, 1999
• 250: Jeffrey Scott Vitter , Philippe Flajolet, Average-case analysis of algorithms and data structures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 251: Jeffrey Scott Vitter , David A. Hutchinson, Distribution sort with randomized cycle, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.77-86, January 07-09, 2001, Washington, D.C., United States
• 252: Jeffrey Scott Vitter , Mark H. Nodine, Large-scale sorting in uniform memory hierarchies, Journal of Parallel and Distributed Computing, v.17 n.1-2, p.107-114, Jan./Feb. 1993 [doi>10.1006/jpdc.1993.1008]
• 253: VITTER,J.S.AND SHRIVER, E. A. M. 1994a. Algorithms for parallel memory I: Two-level memories. Algorithmica 12, 2-3, 110-147.
• 254: VITTER,J.S.AND SHRIVER, E. A. M. 1994b. Algorithms for parallel memory II: Hierarchical multilevel memories. Algorithmica 12, 2-3, 148- 169.
• 255: VITTER,J.S.AND VENGROFF, D. E. 1999. Notes.
• 256: Jeffrey Scott Vitter , Min Wang, Approximate computation of multidimensional aggregates of sparse data using wavelets, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.193-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 257: Jeffrey Scott Vitter , Min Wang , Bala Iyer, Data cube approximation and histograms via wavelets, Proceedings of the seventh international conference on Information and knowledge management, p.96-104, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288645]
• 258: M. Wang , B. Iyer , J. S. Vitter, Scalable Mining for Classification Rules in Relational Databases, Proceedings of the 1998 International Symposium on Database Engineering & Applications, p.58, July 08-10, 1998
• 259: WANG, M., VITTER,J.S.,LIM, L., AND PADMANABHAN,S. 2001. Wavelet-based cost estimation for spatial queries, July.
• 260: R. W. Watson , R. A. Coyne, The parallel I/O architecture of the high-performance storage system (HPSS), Proceedings of the 14th IEEE Symposium on Mass Storage Systems, p.27, September 11-14, 1995
• 261: WEINER, P. 1973. Linear pattern matching algorithm. In Proceedings of the IEEE Symposium on Switching and Automata Theory (Washington, DC), Vol. 14, 1-11.
• 262: Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985 [doi>10.1145/3828.3839]
• 263: Ouri Wolfson , Prasad Sistla , Bo Xu , Jutai Zhou , Sam Chamberlain, DOMINO: databases fOr MovINg Objects tracking, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.547-549, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 264: WOMBLE, D., GREENBERG, D., WHEAT,S.,AND RIESEN,R. 1993. Beyond core: Making parallel computer I/O practical. In Proceedings of the DAGS Symposium on Parallel Computation (Hanover, NH, June), 56-63. Vol. 2, Dartmouth Institute for Advanced Graduate Studies.
• 265: WU,C.,AND FENG, T. 1981. The universality of the shuffle-exchange network. IEEE Transactions on Computers C-30 (May), 324-332.
• 266: YAO, A. C. 1978. On random 2-3 trees. Acta Informatica 9, 159-170.
• 267: Stanley B. Zdonik , David Maier, Readings in object-oriented database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 268: Weiye Zhang , Per-Åke Larson, Dynamic Memory Adjustment for External Mergesort, Proceedings of the 23rd International Conference on Very Large Data Bases, p.376-385, August 25-29, 1997
• 269: Binhai Zhu, Further Computational Geometry in Secondary Memory, Proceedings of the 5th International Symposium on Algorithms and Computation, p.514-522, August 25-27, 1994

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Parallel I/O

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks; Trees
  E.5 FILES
      Subjects: Sorting/searching

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines); Relations between models
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations; Sorting and searching

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods
      H.2.8 Database applications
          Subjects: Spatial databases and GIS
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process; Information filtering

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
B-tree, I/O, batched, block, disk, dynamic, extendible hashing, external memory, hierarchical memory, multidimensional access methods, multilevel memory, online, out-of-core, secondary storage, sorting