Algorithms and data structures for external memory

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.

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.

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.

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.

REFERENCES

• 1: D. J. Abel, "A B⁺-tree structure for large quadtrees," Computer Vision, Graphics, and Image Processing, vol. 27, pp. 19-31, July 1984.
• 2: J. Abello, A. L. Buchsbaum, and J. Westbrook, "A functional approach to external graph algorithms," Algorithmica, vol. 32, no. 3, pp. 437-458, 2002.
• 3: James Abello , Panos M. Pardalos , Mauricio G. C. Resende, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
• 4: 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
• 5: 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
• 6: 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
• 7: P. K. Agarwal, L. Arge, and A. Danner, "From LIDAR to GRID DEM: A scalable approach," in Proceedings of the International Symposium on Spatial Data Handling, 2006.
• 8: Pankaj K. Agarwal , Lars Arge , Jeff Erickson, Indexing moving points, Journal of Computer and System Sciences, v.66 n.1, p.207-243, 01 February 2003 [doi>10.1016/S0022-0000(02)00035-1]
• 9: Pankaj K. Agarwal , Lars Arge , Jeff Erickson , Paulo G. Franciosa , Jeffrey Scott Vitter, Efficient searching with linear constraints, Journal of Computer and System Sciences, v.61 n.2, p.194-216, Oct. 2000 [doi>10.1006/jcss.2000.1709]
• 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 , Lars Arge , Jan Vahrenhold, Time Responsive External Data Structures for Moving Points, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.50-61, August 08-10, 2001
• 13: P. K. Agarwal, L. Arge, J. Yang, and K. Yi, "I/O-efficient structures for orthogonal range-max and stabbing-max queries," in Proceedings of the European Symposium on Algorithms, pp. 7-18, Springer-Verlag, 2003.
• 14: P. K. Agarwal, L. Arge, and K. Yi, "I/O-efficient construction of constrained delaunay triangulations," in Proceedings of the European Symposium on Algorithms , pp. 355-366, Springer-Verlag, 2005.
• 15: Pankaj K. Agarwal , Lars Arge , Ke Yi, An optimal dynamic interval stabbing-max data structure?, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 16: Pankaj K. Agarwal , Lars Arge , Ke Yi, I/O-efficient batched union-find and its applications to terrain analysis, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137884]
• 17: P. K. Agarwal, M. de Berg, J. Gudmundsson, M. Hammar, and H. J. Haverkort, "Box-trees and R-trees with near-optimal query time," Discrete and Computational Geometry, vol. 28, no. 3, pp. 291-312, 2002.
• 18: P. K. Agarwal and J. Erickson, "Geometric range searching and its relatives," in Advances in Discrete and Computational Geometry, (B. Chazelle, J. E. Goodman, and R. Pollack, eds.), pp. 1-56, Providence, Rhode Island: American Mathematical Society Press, 1999.
• 19: 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
• 20: A. Aggarwal , B. Alpern , A. Chandra , M. Snir, A model for hierarchical memory, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.305-314, January 1987, New York, New York, United States [doi>10.1145/28395.28428]
• 21: A. Aggarwal, A. Chandra, and M. Snir, "Hierarchical memory with block transfer," in Proceedings of the IEEE Symposium on Foundations of Computer Science, pp. 204-216, Los Angeles, 1987.
• 22: 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
• 23: 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]
• 24: Charu C. Aggarwal, Data Streams: Models and Algorithms (Advances in Database Systems), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 25: 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]
• 26: D. Ajwani, I. Malinger, U. Meyer, and S. Toledo, "Characterizing the performance of flash memory storage devices and its impact on algorithm design," in Proceedings of the International Workshop on Experimental Algorithmics, (Provincetown, Mass.), pp. 208-219, Springer-Verlag, 2008.
• 27: D. Ajwani, U. Meyer, and V. Osipov, "Improved external memory BFS implementation," in Proceedings of the Workshop on Algorithm Engineering and Experiments, (New Orleans), pp. 3-12, January 2007.
• 28: Susanne Albers , Markus Büttner, Integrated prefetching and caching in single and parallel disk systems, Information and Computation, v.198 n.1, p.24-39, April 10, 2005 [doi>10.1016/j.ic.2005.01.003]
• 29: B. Alpern, L. Carter, E. Feig, and T. Selker, "The uniform memory hierarchy model of computation," Algorithmica, vol. 12, no. 2-3, pp. 72-109, 1994.
• 30: 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
• 31: Lars Arge, External memory data structures, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
• 32: L. Arge, "The buffer tree: A technique for designing batched external data structures," Algorithmica, vol. 37, no. 1, pp. 1-24, 2003.
• 33: L. Arge, G. Brodal, and R. Fagerberg, "Cache-oblivious data structures," in Handbook on Data Structures and Applications, (D. Mehta and S. Sahni, eds.), CRC Press, 2005.
• 34: Lars Arge , Gerth Stølting Brodal , Laura Toma, On external-memory MST, SSSP and multi-way planar graph separation, Journal of Algorithms, v.53 n.2, p.186-206, November 2004 [doi>10.1016/j.jalgor.2004.04.001]
• 35: Lars Arge , Jeffrey S. Chase , Patrick Halpin , Laura Toma , Jeffrey S. Vitter , Dean Urban , Rajiv Wickremesinghe, Efficient Flow Computation on Massive Grid Terrain Datasets, Geoinformatica, v.7 n.4, p.283-313, December 2003 [doi>10.1023/A:1025526421410]
• 36: L. Arge, A. Danner, H. J. Haverkort, and N. Zeh, "I/O-efficient hierarchical watershed decomposition of grid terrains models," in Proceedings of the International Symposium on Spatial Data Handling, 2006.
• 37: L. Arge, A. Danner, and S.-H. Teh, "I/O-efficient point location using persistent B-trees," in Workshop on Algorithm Engineering and Experimentation, 2003.
• 38: Lars Arge , Mark de Berg , Herman J. Haverkort , Ke Yi, The Priority R-tree: a practically efficient and worst-case optimal R-tree, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007608]
• 39: 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]
• 40: L. Arge, M. T. Goodrich, M. Nelson, and N. Sitchinava, "Fundamental parallel algorithms for private-cache chip multiprocessors," in Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, Munich: ACM Press, June 2008.
• 41: L. Arge, K. H. Hinrichs, J. Vahrenhold, and J. S. Vitter, "Efficient bulk operations on dynamic R-trees," Algorithmica, vol. 33, pp. 104-128, January 2002.
• 42: 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
• 43: L. Arge, U. Meyer, and L. Toma, "External memory algorithms for diameter and all-pairs shortest-paths on sparse graphs," in Proceedings of the International Colloquium on Automata, Languages, and Programming, pp. 146-157, Springer-Verlag, 2004.
• 44: L. Arge, U. Meyer, L. Toma, and N. Zeh, "On external-memory planar depth first search," Journal of Graph Algorithms and Applications, vol. 7, no. 2, pp. 105-129, 2003.
• 45: Lars Arge , Peter Bro Miltersen, On showing lower bounds for external-memory computational geometry problems, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 46: 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
• 47: 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
• 48: 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
• 49: Lars Arge , Octavian Procopiuc , Jeffrey Scott Vitter, Implementing I/O-efficient Data Structures Using TPIE, Proceedings of the 10th Annual European Symposium on Algorithms, p.88-100, September 17-21, 2002
• 50: 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]
• 51: L. Arge, V. Samoladas, and K. Yi, "Optimal external memory planar point enclosure," in Proceedings of the European Symposium on Algorithms, pp. 40-52, Springer-Verlag, 2004.
• 52: L. Arge and L. Toma, "Simplified external memory algorithms for planar DAGs," in Proceedings of the Scandinavian Workshop on Algorithmic Theory, pp. 493-503, 2004.
• 53: L. Arge and L. Toma, "External data structures for shortest path queries on planar digraphs," in Proceedings of the International Symposium on Algorithms and Computation, pp. 328-338, Springer-Verlag, 2005.
• 54: L. Arge, L. Toma, and J. S. Vitter, "I/O-efficient algorithms for problems on grid-based terrains," in Workshop on Algorithm Engineering and Experimentation , San Francisco: Springer-Verlag, January 2000.
• 55: Lars Arge , Laura Toma , Norbert Zeh, I/O-efficient topological sorting of planar DAGs, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777427]
• 56: Lars Arge , Jan Vahrenhold, I/O-efficient dynamic planar point location, Computational Geometry: Theory and Applications, v.29 n.2, p.147-162, October 2004 [doi>10.1016/j.comgeo.2003.04.001]
• 57: Lars Arge , Darren Erik Vengroff , Jeffrey Scott Vitter, External-Memory Algorithms for Processing Line Segments in Geographic Information Systems, Algorithmica, v.47 n.1, p.1-25, January 2007 [doi>10.1007/s00453-006-1208-z]
• 58: Lars Arge , Jeffrey Scott Vitter, Optimal External Memory Interval Management, SIAM Journal on Computing, v.32 n.6, p.1488-1508, 2003 [doi>10.1137/S009753970240481X]
• 59: Lars Arge , Norbert Zeh, I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.261, October 11-14, 2003
• 60: 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]
• 61: D. Arroyuelo and G. Navarro, "A Lempel-Ziv text index on secondary storage," in Proceedings of the Symposium on Combinatorial Pattern Matching, pp. 83-94, Springer-Verlag, 2007.
• 62: Mikhail J. Atallah , Sunil Prabhakar, (Almost) Optimal parallel block access for range queries, Information Sciences—Informatics and Computer Science: An International Journal, v.157 n.1-2, p.21-31, December 2003 [doi>10.1016/S0020-0255(03)00181-6]
• 63: 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]
• 64: Ricardo A. Baeza-Yates, Bounded disorder: the effect of the index, Theoretical Computer Science, v.168 n.1, p.21-38, Nov. 10, 1996
• 65: 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]
• 66: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 67: 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
• 68: 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]
• 69: 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]
• 70: 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
• 71: 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
• 72: R. D. Barve and J. S. Vitter, "A simple and efficient parallel disk mergesort," ACM Trans. Computer Systems, vol. 35, pp. 189-215, March/April 2002.
• 73: 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]
• 74: R. Bayer and E. McCreight, "Organization of large ordered indexes," Acta Informatica, vol. 1, pp. 173-189, 1972.
• 75: 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]
• 76: 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]
• 77: 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
• 78: A. L. Belady, "A study of replacement algorithms for virtual storage computers," IBM Systems Journal, vol. 5, pp. 78-101, 1966.
• 79: Michael A. Bender , Erik D. Demaine , Martin Farach-Colton, Cache-Oblivious B-Trees, SIAM Journal on Computing, v.35 n.2, p.341-358, 2005 [doi>10.1137/S0097539701389956]
• 80: Michael A. Bender , Martin Farach-Colton , Bradley C. Kuszmaul, Cache-oblivious string B-trees, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142385]
• 81: Michael A. Bender , Jeremy T. Fineman , Seth Gilbert , Bradley C. Kuszmaul, Concurrent cache-oblivious b-trees, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074009]
• 82: 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]
• 83: J. L. Bentley and J. B. Saxe, "Decomposable searching problems I: Static-to-dynamic transformations," Journal of Algorithms, vol. 1, pp. 301-358, December 1980.
• 84: 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
• 85: Mette Berger , Esben Rune Hansen , Rasmus Pagh , Mihai Pǎtraşcu , Milan Ružić , Peter Tiedemann, Deterministic load balancing and dictionaries in the parallel disk model, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148160]
• 86: R. Bhatia, R. K. Sinha, and C.-M. Chen, "A hierarchical technique for constructing efficient declustering schemes for range queries," The Computer Journal, vol. 46, no. 4, pp. 358-377, 2003.
• 87: N. Blum and K. Mehlhorn, "On the average number of rebalancing operations in weight-balanced trees," Theoretical Computer Science, vol. 11, pp. 303-320, July 1980.
• 88: 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]
• 89: C. Breimann and J. Vahrenhold, "External memory computational geometry revisited," in Algorithms for Memory Hierarchies, pp. 110-148, 2002.
• 90: Klaus Brengel , Andreas Crauser , Paolo Ferragina , Ulrich Meyer, An experimental study of priority queues in external memory, Journal of Experimental Algorithmics (JEA), 5, p.17-es, 2000 [doi>10.1145/351827.384259]
• 91: Gerth Stolting Brodal , Rolf Fagerberg, Lower bounds for external memory dictionaries, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 92: 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
• 93: 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
• 94: 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
• 95: Pei Cao , Edward W. Felten , Anna R. Karlin , Kai Li, Implementation and performance of integrated application-controlled file caching, prefetching, and disk scheduling, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.311-343, Nov. 1996 [doi>10.1145/235543.235544]
• 96: 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
• 97: G. Chaudhry and T. H. Cormen, "Oblivious vs. distribution-based sorting: An experimental evaluation," in Proceedings of the European Symposium on Algorithms, pp. 317-328, Springer-Verlag, 2005.
• 98: 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]
• 99: 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]
• 100: B. Chazelle and H. Edelsbrunner, "Linear space data structures for two types of range search," Discrete and Computational Geometry, vol. 2, pp. 113-126, 1987.
• 101: 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]
• 102: Reynold Cheng , Yuni Xia , Sunil Prabhakar , Rahul Shah , Jeffrey Scott Vitter, Efficient indexing methods for probabilistic threshold queries over uncertain data, Proceedings of the Thirtieth international conference on Very large data bases, p.876-887, August 31-September 03, 2004, Toronto, Canada
• 103: Reynold Cheng , Sarvjeet Singh , Sunil Prabhakar , Rahul Shah , Jeffrey Scott Vitter , Yuni Xia, Efficient join processing over uncertain data, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183719]
• 104: 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]
• 105: 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
• 106: 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
• 107: Y.-F. Chien, W.-K. Hon, R. Shah, and J. S. Vitter, "Geometric Burrows-Wheeler transform: Linking range searching and text indexing," in Proceedings of the Data Compression Conference, Snowbird, Utah: IEEE Computer Society Press, March 2008.
• 108: Rezaul Alam Chowdhury , Vijaya Ramachandran, External-memory exact and approximate all-pairs shortest-paths in undirected graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 109: Valentina Ciriani , Paolo Ferragina , Fabrizio Luccio , S. Muthukrishnan, Static Optimality Theorem for External Memory String Access, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.219-227, November 16-19, 2002
• 110: 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
• 111: 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]
• 112: F. Claude and G. Navarro, "A fast and compact Web graph representation," in Proceedings of the International Symposium on String Processing and Information Retrieval, pp. 105-116, Springer-Verlag, 2007.
• 113: 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
• 114: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 115: P. Corbett, D. Feitelson, S. Fineberg, Y. Hsu, B. Nitzberg, J.-P. Prost, M. Snir, B. Traversat, and P. Wong, "Overview of the MPI-IO parallel I/O interface," in Input/Output in Parallel and Distributed Computer Systems, (R. Jain, J. Werth, and J. C. Browne, eds.), ch. 5, pp. 127-146, Kluwer Academic Publishers, 1996.
• 116: 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]
• 117: T. H. Cormen and E. R. Davidson, "FG: A framework generator for hiding latency in parallel programs running on clusters," in Proceedings of the 17th International Conference on Parallel and Distributed Computing Systems , pp. 137-144, Sep. 2004.
• 118: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 119: 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]
• 120: 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]
• 121: A. Crauser and P. Ferragina, "A theoretical and experimental study on the construction of suffix arrays in external memory," Algorithmica, vol. 32, no. 1, pp. 1-35, 2002.
• 122: 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
• 123: A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer, and E. A. Ramos, "Randomized external-memory algorithms for line segment intersection and other geometric problems," International Journal of Computational Geometry and Applications, vol. 11, no. 3, pp. 305-337, 2001.
• 124: 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
• 125: Kenneth M. Curewitz , P. Krishnan , Jeffrey Scott Vitter, Practical prefetching via data compression, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.257-266, May 25-28, 1993, Washington, D.C., United States
• 126: 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]
• 127: E. R. Davidson, FG: Improving Parallel Programs and Parallel Programming Since 2003. PhD thesis, Dartmouth College Department of Computer Science, Aug. 2006.
• 128: M. de Berg , J. Gudmundsson , M. Hammar , M. Overmars, On R-trees with low query complexity, Computational Geometry: Theory and Applications, v.24 n.3, p.179-195, April 2003 [doi>10.1016/S0925-7721(02)00112-8]
• 129: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 130: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 131: F. K. H. A. Dehne, W. Dittrich, and D. A. Hutchinson, "Efficient External Memory Algorithms by Simulating Coarse-Grained Parallel Algorithms," Algorithmica, vol. 36, no. 2, pp. 97-122, 2003.
• 132: F. K. H. A. Dehne, W. Dittrich, D. A. Hutchinson, and A. Maheshwari, "Bulk synchronous parallel algorithms for the external memory model," Theory of Computing Systems, vol. 35, no. 6, pp. 567-597, 2002.
• 133: R. Dementiev, Algorithm Engineering for Large Data Sets. PhD thesis, Saarland University, 2006.
• 134: R. Dementiev, J. Kärkkäinen, J. Mehnert, and P. Sanders, "Better external memory suffix array construction," ACM Journal of Experimental Algorithmics , in press.
• 135: R. Dementiev , L. Kettner , P. Sanders, STXXL: standard template library for XXL data sets, Software—Practice & Experience, v.38 n.6, p.589-637, May 2008 [doi>10.1002/spe.v38:6]
• 136: Roman Dementiev , Peter Sanders, Asynchronous parallel disk sorting, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777435]
• 137: R. Dementiev, P. Sanders, D. Schultes, and J. Sibeyn, "Engineering an external memory minimum spanning tree algorithm," in Proceedings of IFIP International Conference on Theoretical Computer Science, Toulouse: Kluwer Academic Publishers, 2004.
• 138: H. B. Demuth, Electronic data sorting. PhD thesis, Stanford University, 1956.
• 139: P. J. Denning, Working Sets Past and Present, IEEE Transactions on Software Engineering, v.6 n.1, p.64-84, January 1980 [doi>10.1109/TSE.1980.230464]
• 140: 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
• 141: W. Dittrich, D. A. Hutchinson, and A. Maheshwari, "Blocking in parallel multisearch problems," Theory of Computing Systems, vol. 34, no. 2, pp. 145-189, 2001.
• 142: 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]
• 143: 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
• 144: H. Edelsbrunner, "A new approach to rectangle intersections, Part I," International Journal of Computer Mathematics, vol. 13, pp. 209-219, 1983.
• 145: H. Edelsbrunner, "A New approach to rectangle intersections, Part II," International Journal of Computer Mathematics, vol. 13, pp. 221-229, 1983.
• 146: Mohamed Y. Eltabakh , Wing-Kai Hon , Rahul Shah , Walid G. Aref , Jeffrey S. Vitter, The SBC-tree: an index for run-length compressed sequences, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353407]
• 147: 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]
• 148: "NASA's Earth Observing System (EOS) web page, NASA Goddard Space Flight Center," http://eospso.gsfc.nasa.gov/.
• 149: 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]
• 150: Jeff Erickson, Lower bounds for external algebraic decision trees, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 151: 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]
• 152: R. Fagerberg, A. Pagh, and R. Pagh, "External string sorting: Faster and cache oblivious," in Proceedings of the Symposium on Theoretical Aspects of Computer Science, pp. 68-79, Springer-Verlag, 2006.
• 153: 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]
• 154: Martin Farach-Colton , Paolo Ferragina , S. Muthukrishnan, On the sorting-complexity of suffix tree construction, Journal of the ACM (JACM), v.47 n.6, p.987-1011, Nov. 2000 [doi>10.1145/355541.355547]
• 155: Joan Feigenbaum , Sampath Kannan , Martin J. Strauss , Mahesh Viswanathan, An Approximate L¹-Difference Algorithm for Massive Data Streams, SIAM Journal on Computing, v.32 n.1, p.131-151, 2003 [doi>10.1137/S0097539799361701]
• 156: W. Feller, An Introduction to Probability Theory and its Applications. Vol. 1, New York: John Wiley & Sons, 3rd ed., 1968.
• 157: 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
• 158: 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]
• 159: P. Ferragina, R. Grossi, A. Gupta, R. Shah, and J. S. Vitter, "On searching compressed string collections cache-obliviously," in Proceedings of the ACM Conference on Principles of Database Systems, Vancouver: ACM Press, June 2008.
• 160: Paolo Ferragina , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Two-dimensional substring indexing, Journal of Computer and System Sciences, v.66 n.4, p.763-774, 1 June 2003 [doi>10.1016/S0022-0000(03)00028-X]
• 161: 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]
• 162: Paolo Ferragina , Giovanni Manzini, Indexing compressed text, Journal of the ACM (JACM), v.52 n.4, p.552-581, July 2005 [doi>10.1145/1082036.1082039]
• 163: Paolo Ferragina , Giovanni Manzini , Veli Mäkinen , Gonzalo Navarro, Compressed representations of sequences and full-text indexes, ACM Transactions on Algorithms (TALG), v.3 n.2, p.20-es, May 2007 [doi>10.1145/1240233.1240243]
• 164: P. Flajolet, "On the performance evaluation of extendible hashing and trie searching," Acta Informatica, vol. 20, no. 4, pp. 345-369, 1983.
• 165: R. W. Floyd, "Permuting information in idealized two-level storage," in Complexity of Computer Computations, (R. Miller and J. Thatcher, eds.), pp. 105-109, Plenum, 1972.
• 166: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 167: Gianni Franceschini , Roberto Grossi , J. Ian Munro , Linda Pagli, Implicit B-trees: a new data structure for the dictionary problem, Journal of Computer and System Sciences, v.68 n.4, p.788-807, June 2004 [doi>10.1016/j.jcss.2003.11.003]
• 168: 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
• 169: 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]
• 170: 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]
• 171: G. R. Ganger, "Generating representative synthetic workloads: An unsolved problem," in Proceedings of the Computer Measurement Group Conference, pp. 1263-1269, December 1995.
• 172: M. Gardner, ch. 7, Magic Show. New York: Knopf, 1977.
• 173: 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]
• 174: Thanaa M. Ghanem , Rahul Shah , Mohamed F. Mokbel , Walid G. Aref , Jeffrey S. Vitter, Bulk Operations for Space-Partitioning Trees, Proceedings of the 20th International Conference on Data Engineering, p.29, March 30-April 02, 2004
• 175: 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]
• 176: 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
• 177: 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
• 178: R. González and G. Navarro, "A compressed text index on secondary memory," in Proceedings of the International Workshop on Combinatorial Algorithms , (Newcastle, Australia), pp. 80-91, College Publications, 2007.
• 179: M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter, "External-memory computational geometry," in Proceedings of the IEEE Symposium on Foundations of Computer Science, pp. 714-723, Palo Alto: IEEE Computer Society Press, November 1993.
• 180: "Google Earth online database of satellite images," Available on the World-Wide Web at http://earth.google.com/.
• 181: Sathish Govindarajan , Pankaj K. Agarwal , Lars Arge, CRB-Tree: An Efficient Indexing Scheme for Range-Aggregate Queries, Proceedings of the 9th International Conference on Database Theory, p.143-157, January 08-10, 2003
• 182: Sathish Govindarajan , Tamas Lukovszki , Anil Maheshwari , Norbert Zeh, I/O-Efficient Well-Separated Pair Decomposition and Applications, Algorithmica, v.45 n.4, p.585-614, August 2006 [doi>10.1007/s00453-005-1197-3]
• 183: 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
• 184: 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
• 185: Roberto Grossi , Ankur Gupta , Jeffrey Scott Vitter, High-order entropy-compressed text indexes, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 186: Roberto Grossi , Giuseppe F. Italiano, Efficient cross-trees for external memory, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 187: Roberto Grossi , Giuseppe F. Italiano, Efficient splitting and merging algorithms for order decomposable problems, Information and Computation, v.154 n.1, p.1-33, Oct. 10, 1999 [doi>10.1006/inco.1999.2811]
• 188: S. K. S. Gupta, Z. Li, and J. H. Reif, "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, pp. 510-513, October 1995.
• 189: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 190: 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
• 191: H. J. Haverkort and L. Toma, "I/O-efficient algorithms on near-planar graphs," in Proceedings of the Latin American Theoretical Informatics Symposium , pp. 580-591, 2006.
• 192: Tom Hazel , Laura Toma , Jan Vahrenhold , Rajiv Wickremesinghe, TerraCost: a versatile and scalable approach to computing least-cost-path surfaces for massive grid-based terrains, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France [doi>10.1145/1141277.1141290]
• 193: 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]
• 194: L. Hellerstein, G. Gibson, R. M. Karp, R. H. Katz, and D. A. Patterson, "Coding techniques for handling failures in large disk arrays," Algorithmica, vol. 12, no. 2-3, pp. 182-208, 1994.
• 195: Monika R. Henzinger , Prabhakar Raghavan , Sridhar Rajagopalan, Computing on data streams, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 196: Klaus Hinrichs, Implementation of the grid file: design concepts and experience, BIT, v.25 n.4, p.569-592, 1985 [doi>10.1007/BF01936137]
• 197: W.-K. Hon, T.-W. Lam, R. Shah, S.-L. Tam, and J. S. Vitter, "Cache-oblivious index for approximate string matching," in Proceedings of the Symposium on Combinatorial Pattern Matching, pp. 40-51, London, Ontario, Canada: Springer-Verlag, July 2007.
• 198: W.-K. Hon, R. Shah, P. J. Varman, and J. S. Vitter, "Tight competitive ratios for parallel disk prefetching and caching," in Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, Munich: ACM Press, June 2008.
• 199: 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]
• 200: D. Hutchinson, A. Maheshwari, J.-R. Sack, and R. Velicescu, "Early experiences in implementing the buffer tree," in Proceedings of the Workshop on Algorithm Engineering, Springer-Verlag, 1997.
• 201: David Hutchinson , Anil Maheshwari , Norbert Zeh, An external memory data structure for shortest path queries, Discrete Applied Mathematics, v.126 n.1, p.55-82, March 2003 [doi>10.1016/S0166-218X(02)00217-2]
• 202: David A. Hutchinson , Peter Sanders , Jeffrey Scott Vitter, Duality Between Prefetching and Queued Writing with Parallel Disks, SIAM Journal on Computing, v.34 n.6, p.1443-1463, 2005 [doi>10.1137/S0097539703431573]
• 203: 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]
• 204: 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]
• 205: Mahesh Kallahalla , Peter J. Varman, Optimal Read-Once Parallel Disk Scheduling, Algorithmica, v.43 n.4, p.309-343, December 2005 [doi>10.1007/s00453-004-1129-7]
• 206: 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]
• 207: 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
• 208: I. Kamel, M. Khalil, and V. Kouramajian, "Bulk insertion in dynamic R-trees," in Proceedings of the International Symposium on Spatial Data Handling , pp. 3B, 31-42, 1996.
• 209: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages, Journal of Computer and System Sciences, v.51 n.1, p.26-52, Aug. 1995
• 210: 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]
• 211: Kothuri Venkata Ravi Kanth , Ambuj K. Singh, Optimal Dynamic Range Searching in Non-replicating Index Structures, Proceedings of the 7th International Conference on Database Theory, p.257-276, January 10-12, 1999
• 212: J. Kärkkäinen and S. S. Rao, "Full-text indexes in external memory," in Algorithms for Memory Hierarchies, (U. Meyer, P. Sanders, and J. Sibeyn, eds.), ch. 7, pp. 149-170, Berlin: Springer-Verlag, 2003.
• 213: I. Katriel and U. Meyer, "Elementary graph algorithms in external memory," in Algorithms for Memory Hierarchies, (U. Meyer, P. Sanders, and J. Sibeyn, eds.), ch. 4, pp. 62-84, Berlin: Springer-Verlag, 2003.
• 214: R. Khandekar and V. Pandit, "Offline Sorting Buffers On Line," in Proceedings of the International Symposium on Algorithms and Computation, pp. 81-89, Springer-Verlag, December 2006.
• 215: Samir Khuller , Yoo-Ah Kim, Algorithms for Data Migration with Cloning, SIAM Journal on Computing, v.33 n.2, p.448-461, 2004 [doi>10.1137/S009753970342585X]
• 216: M Y Kim, Synchronized Disk Interleaving, IEEE Transactions on Computers, v.35 n.11, p.978-988, November 1986 [doi>10.1109/TC.1986.1676699]
• 217: Tracy Kimbrel , Anna R. Karlin, Near-Optimal Parallel Prefetching and Caching, SIAM Journal on Computing, v.29 n.4, p.1051-1082, Feb. 2000 to March 2000 [doi>10.1137/S0097539797326976]
• 218: 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]
• 219: Shmuel T. Klein , Dana Shapira, Searching in Compressed Dictionaries, Proceedings of the Data Compression Conference (DCC '02), p.142, April 02-04, 2002
• 220: 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
• 221: D. E. Knuth, MMIXware. Berlin: Springer-Verlag, 1999.
• 222: D. E. Knuth, J. H. Morris, and V. R. Pratt, "Fast pattern matching in strings," SIAM Journal on Computing, vol. 6, pp. 323-350, 1977.
• 223: 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]
• 224: 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]
• 225: M. Kowarschik and C. Weiß, "An overview of cache optimizaiton techniques and cache-aware numerical algorithms," in Algorithms for Memory Hierarchies , (U. Meyer, P. Sanders, and J. Sibeyn, eds.), ch. 10, pp. 213-232, Berlin: Springer-Verlag, 2003.
• 226: P. Krishnan , Jeffrey Scott Vitter, Optimal Prediction for Prefetching in the Worst Case, SIAM Journal on Computing, v.27 n.6, p.1617-1636, Dec. 1998 [doi>10.1137/S0097539794261817]
• 227: 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
• 228: K. Küspert, "Storage utilization in B*-trees with a generalized overflow technique," Acta Informatica, vol. 19, pp. 35-55, 1983.
• 229: 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]
• 230: R. Laurini and D. Thompson, Fundamentals of Spatial Information Systems. Academic Press, 1992.
• 231: 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]
• 232: 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]
• 233: Charles E. Leiserson , Satish Rao , Sivan Toledo, Efficient out-of-core algorithms for linear relaxation using blocking covers, Journal of Computer and System Sciences, v.54 n.2, p.332-344, April 1997 [doi>10.1006/jcss.1997.1473]
• 234: Z. Li, P. H. Mills, and J. H. Reif, "Models and resource metrics for parallel and distributed computation," Parallel Algorithms and Applications, vol. 8, pp. 35-59, 1996.
• 235: Witold Litwin, Linear hashing: a new tool for file and table addressing, Proceedings of the sixth international conference on Very Large Data Bases, p.212-223, October 01-03, 1980, Montreal, Quebec, Canada
• 236: W. Litwin , D. B. Lomet, A New Method for Fast Data Searches with Keys, IEEE Software, v.4 n.2, p.16-24, March 1987 [doi>10.1109/MS.1987.230092]
• 237: 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]
• 238: 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]
• 239: 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]
• 240: Tamás Lukovszki , Anil Maheshwari , Norbert Zeh, I/O-Efficient Batched Range Counting and Its Applications to Proximity Problems, Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science, p.244-255, December 13-15, 2001
• 241: 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
• 242: Anil Maheshwari , Norbert Zeh, I/O-optimal algorithms for planar graphs using separators, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.372-381, January 06-08, 2002, San Francisco, California
• 243: A. Maheshwari and N. Zeh, "A survey of techniques for designing I/O-efficient algorithms," in Algorithms for Memory Hierarchies, (U. Meyer, P. Sanders, and J. Sibeyn, eds.), ch. 3, pp. 36-61, Berlin: Springer-Verlag, 2003.
• 244: A. Maheshwari and N. Zeh, "I/O-optimal algorithms for outerplanar graphs," Journal of Graph Algorithms and Applications, vol. 8, pp. 47-87, 2004.
• 245: V. Mäkinen, G. Navarro, and K. Sadakane, "Advantages of backward searching --efficient secondary memory and distributed implementation of compressed suffix arrays," in Proceedings of the International Symposium on Algorithms and Computation, pp. 681-692, Springer-Verlag, 2004.
• 246: 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]
• 247: Udi Manber , Sun Wu, GLIMPSE: a tool to search through entire file systems, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.4-4, January 17-21, 1994, San Francisco, California
• 248: G. N.N. Martin, Spiral Storage: Incrementally Augmentable Hash Addressed Storage, University of Warwick, Coventry, UK, 1979
• 249: 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
• 250: 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]
• 251: E. M. McCreight, "Priority Search Trees," SIAM Journal on Computing, vol. 14, pp. 257-276, May 1985.
• 252: Kurt Mehlhorn , Ulrich Meyer, External-Memory Breadth-First Search with Sublinear I/O, Proceedings of the 10th Annual European Symposium on Algorithms, p.723-735, September 17-21, 2002
• 253: H. Mendelson, Analysis of Extendible Hashing, IEEE Transactions on Software Engineering, v.8 n.6, p.611-619, November 1982 [doi>10.1109/TSE.1982.236022]
• 254: 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
• 255: U. Meyer, "On dynamic breadth-first search in external-memory," in Proceedings of the Symposium on Theoretical Aspects of Computer Science, (Schloss Dagstuhl, Germany), pp. 551-560, Internationales Begegnungs- und Forschungszentrum für Informatik, 2008.
• 256: U. Meyer, "On trade-offs in external-memory diameter approximation," in Proceedings of the Scandinavian Workshop on Algorithm Theory, (Gothenburg, Sweden), Springer-Verlag, July 2008.
• 257: Ulrich Meyer , Peter Sanders , Jop Sibeyn, Algorithms for Memory Hierarchies, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 258: Ulrich Meyer , Norbert Zeh, I/O-efficient undirected shortest paths with unbounded edge lengths, Proceedings of the 14th conference on Annual European Symposium, p.540-551, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_49]
• 259: Ulrich Meyer , Norbert Zeh, I/O-efficient undirected shortest paths with unbounded edge lengths, Proceedings of the 14th conference on Annual European Symposium, p.540-551, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_49]
• 260: C. Mohan, ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes, Proceedings of the 16th International Conference on Very Large Data Bases, p.392-405, August 13-16, 1990
• 261: 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]
• 262: 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]
• 263: J. K. Mullin, "Spiral storage: Efficient dynamic hashing with constant performance," The Computer Journal, vol. 28, pp. 330-334, July 1985.
• 264: 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
• 265: S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005 [doi>10.1561/0400000002]
• 266: Gonzalo Navarro, Indexing text using the Ziv-Lempel trie, Journal of Discrete Algorithms, v.2 n.1, p.87-114, March 2004 [doi>10.1016/S1570-8667(03)00066-2]
• 267: Gonzalo Navarro , Veli Mäkinen, Compressed full-text indexes, ACM Computing Surveys (CSUR), v.39 n.1, p.2-es, 2007 [doi>10.1145/1216370.1216372]
• 268: 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]
• 269: J. Nievergelt and E. M. Reingold, "Binary search tree of bounded balance," SIAM Journal on Computing, vol. 2, pp. 33-43, March 1973.
• 270: 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
• 271: M. H. Nodine, M. T. Goodrich, and J. S. Vitter, "Blocking for external graph searching," Algorithmica, vol. 16, pp. 181-214, August 1996.
• 272: 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]
• 273: 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]
• 274: 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]
• 275: 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]
• 276: 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
• 277: 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]
• 278: Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 279: 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
• 280: 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
• 281: 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]
• 282: 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
• 283: 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
• 284: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 285: O. Procopiuc, P. K. Agarwal, L. Arge, and J. S. Vitter, "Bkd-tree: A dynamic scalable kd-tree," in Proceedings of the International Symposium on Spatial and Temporal Databases, Santorini, Greece: Springer-Verlag, July 2003.
• 286: S. J. Puglisi, W. F. Smyth, and A. Turpin, "Inverted files versus suffix arrays for locating patterns in primary memory," in Proceedings of the International Symposium on String Processing Information Retrieval, pp. 122-133, Springer-Verlag, 2006.
• 287: N. Rahman and R. Raman, "Adapting radix sort to the memory hierarchy," in Workshop on Algorithm Engineering and Experimentation, Springer-Verlag, January 2000.
• 288: Rajeev Raman , Venkatesh Raman , S. Srinivasa Rao, Succinct indexable dictionaries with applications to encoding k-ary trees and multisets, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.233-242, January 06-08, 2002, San Francisco, California
• 289: 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]
• 290: 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
• 291: 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
• 292: 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
• 293: 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]
• 294: 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]
• 295: 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]
• 296: Kenneth Salem , Hector Garcia-Molina, Disk Striping, Proceedings of the Second International Conference on Data Engineering, p.336-342, February 05-07, 1986
• 297: 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
• 298: 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]
• 299: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 300: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 301: 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]
• 302: Peter Sanders, Fast priority queues for cached memory, Journal of Experimental Algorithmics (JEA), 5, p.7-es, 2000 [doi>10.1145/351827.384249]
• 303: P. Sanders, Reconciling simplicity and realism in parallel disk modelsy, Parallel Computing, v.28 n.5, p.705-723, May 2002 [doi>10.1016/S0167-8191(02)00092-3]
• 304: P. Sanders, S. Egner, and J. Korst, "Fast concurrent access to parallel disks," Algorithmica, vol. 35, no. 1, pp. 21-55, 2002.
• 305: 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
• 306: J. E. Savage and J. S. Vitter, "Parallelism in space-time tradeoffs," in Advances in Computing Research, (F. P. Preparata, ed.), pp. 117-146, JAI Press, 1987.
• 307: 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
• 308: 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
• 309: Bernhard Seeger , Hans-Peter Kriegel, The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems, Proceedings of the 16th International Conference on Very Large Data Bases, p.590-601, August 13-16, 1990
• 310: Margo Seltzer , Keith A. Smith , Hari Balakrishnan , Jacqueline Chang , Sara McMains , Venkata Padmanabhan, File system logging versus clustering: a performance comparison, Proceedings of the USENIX 1995 Technical Conference Proceedings on USENIX 1995 Technical Conference Proceedings, p.21-21, January 16-20, 1995, New Orleans, Louisiana
• 311: Sandeep Sen , Siddhartha Chatterjee , Neeraj Dumir, Towards a theory of cache-efficient algorithms, Journal of the ACM (JACM), v.49 n.6, p.828-858, November 2002 [doi>10.1145/602220.602225]
• 312: Rahul Shah , Peter J. Varman , Jeffrey Scott Vitter, Online algorithms for prefetching and caching on parallel disks, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007950]
• 313: Rahul Shah , Peter J. Varman , Jeffrey Scott Vitter, On competitive online read-many parallel disks scheduling, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074006]
• 314: 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
• 315: E. A. M. Shriver and M. H. Nodine, "An introduction to parallel I/O models and algorithms," in Input/Output in Parallel and Distributed Computer Systems , (R. Jain, J. Werth, and J. C. Browne, eds.), ch. 2, pp. 31-68, Kluwer Academic Publishers, 1996.
• 316: Elizabeth A. M. Shriver , Leonard F. Wisniewski, An API for Choreographing Data Accesses, Dartmouth College, Hanover, NH, 1995
• 317: J. F. Sibeyn, "From parallel to external list ranking," Technical Report MPI-I-97-1-021, Max-Planck-Institut, September 1997.
• 318: Jop F. Sibeyn, External selection, Journal of Algorithms, v.58 n.2, p.104-117, February 2006 [doi>10.1016/j.jalgor.2005.02.002]
• 319: 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
• 320: R. Sinha, S. Puglisi, A. Moffat, and A. Turpin, "Improving suffix array locality for fast pattern matching on disk," in Proceedings of the ACM SIGMOD International Conference on Management of Data, Vancouver: ACM Press, June 2008.
• 321: 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]
• 322: 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
• 323: 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
• 324: R. Tamassia and J. S. Vitter, "Optimal cooperative search in fractional cascaded data structures," Algorithmica, vol. 15, pp. 154-171, February 1996.
• 325: "TerraServer-USA: Microsoft's online database of satellite images," Available on the World-Wide Web at http://terraserver.microsoft.com/.
• 326: 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
• 327: "Topologically Integrated Geographic Encoding and Referencing system, TIGER/Line 1992 datafiles," Available on the World-Wide Web at http://www.census.gov/geo/www/tiger/, 1992.
• 328: Sivan Toledo, A survey of out-of-core algorithms in numerical linear algebra, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 329: L. Toma and N. Zeh, "I/O-efficient algorithms for sparse graphs," in Algorithms for Memory Hierarchies, (U. Meyer, P. Sanders, and J. Sibeyn, eds.), ch. 5, pp. 85-109, Berlin: Springer-Verlag, 2003.
• 330: TPIE User Manual and Reference, "The manual and software distribution," available on the web at http://www.cs.duke.edu/TPIE/, 1999.
• 331: J. D. Ullman and M. Yannakakis, "The input/output complexity of transitive closure," Annals of Mathematics and Artificial Intelligence, vol. 3, pp. 331-360, 1991.
• 332: Jan Vahrenhold , Klaus H. Hinrichs, Planar point location for large data sets: to seek or not to seek, Journal of Experimental Algorithmics (JEA), 7, p.8, 2002 [doi>10.1145/944618.944626]
• 333: 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
• 334: M. van Kreveld, J. Nievergelt, T. Roos, and P. Widmayer, eds., Algorithmic foundations of GIS. Vol. 1340 of Lecture Notes in Computer Science, Springer-Verlag, 1997.
• 335: 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]
• 336: 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]
• 337: D. E. Vengroff and J. S. Vitter, "I/O-efficient scientific computation using TPIE," in Proceedings of NASA Goddard Conference on Mass Storage Systems , pp. II, 553-570, September 1996.
• 338: P. Vettiger, M. Despont, U. Drechsler, U. Dürig, W. Häberle, M. I. Lutwyche, E. Rothuizen, R. Stutz, R. Widmer, and G. K. Binnig, "The 'Millipede' -- more than one thousand tips for future AFM data storage," IBM Journal of Research and Development, vol. 44, no. 3, pp. 323-340, 2000.
• 339: 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
• 340: J. S. Vitter, Notes. 1999.
• 341: 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
• 342: Jeffrey Scott Vitter , David Alexander Hutchinson, Distribution sort with randomized cycling, Journal of the ACM (JACM), v.53 n.4, p.656-680, July 2006 [doi>10.1145/1162349.1162352]
• 343: Jeffrey Scott Vitter , P. Krishnan, Optimal prefetching via data compression, Journal of the ACM (JACM), v.43 n.5, p.771-793, Sept. 1996 [doi>10.1145/234752.234753]
• 344: 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]
• 345: J. S. Vitter and E. A. M. Shriver, "Algorithms for parallel memory I: Two-level memories," Algorithmica, vol. 12, no. 2-3, pp. 110-147, 1994.
• 346: J. S. Vitter and E. A. M. Shriver, "Algorithms for parallel memory II: Hierarchical multilevel memories," Algorithmica, vol. 12, no. 2-3, pp. 148-169, 1994.
• 347: 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
• 348: 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]
• 349: M. Wang, B. Iyer, and J. S. Vitter, "Scalable mining for classification rules in relational databases," in Herman Rubin Festschrift, Hayward, CA: Institute of Mathematical Statistics, Fall 2004.
• 350: Min Wang , Jeffrey Scott Vitter , Lipyeow Lim , Sriram Padmanabhan, Wavelet-Based Cost Estimation for Spatial Queries, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.175-196, July 12-15, 2001
• 351: 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
• 352: P. Weiner, "Linear pattern matching algorithm," in Proceedings of the IEEE Symposium on Switching and Automata Theory, pp. 1-11, 1973.
• 353: Kyu-Young Whang , Ravi Krishnamurthy, The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure, Proceedings of the Second International Symposium on Database Systems for Advanced Applications, p.449-459, April 02-04, 1991
• 354: 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]
• 355: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 356: 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
• 357: D. Womble, D. Greenberg, S. Wheat, and R. Riesen, "Beyond core: Making parallel computer I/O practical," in Proceedings of the DAGS Symposium on Parallel Computation, pp. 56-63, June 1993.
• 358: Chuan-Lin Wu , Tse-Yun Feng, The Universality of the Shuffle-Exchange Network, IEEE Transactions on Computers, v.30 n.5, p.324-332, May 1981 [doi>10.1109/TC.1981.1675790]
• 359: Yuni Xia , Sunil Prabhakar , Shan Lei , Reynold Cheng , Rahul Shah, Indexing continuously changing data with mean-variance tree, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066932]
• 360: A. C. Yao, "On random 2-3 trees," Acta Informatica, vol. 9, pp. 159-170, 1978.
• 361: Stanley B. Zdonik , David Maier, Readings in object-oriented database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 362: Norbert Ralf Zeh , Anil Maheshwari , Jorg-Rudiger Sack, I/o-efficient algorithms for shortest path related problems, Carleton University, Ottawa, Ont., Canada, 2002
• 363: 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
• 364: 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
• 365: J. Ziv and A. Lempel, "Compression of individual sequences via variable-rate coding," IEEE Transactions on Information Theory, vol. 24, pp. 530-536, September 1978.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
      D.4.3 File Systems Management
      D.4.4 Communications Management

  E. Data
  E.0 GENERAL

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