Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

External Memory Data Structures

Invited Paper

  • Conference paper
  • First Online:
Algorithms — ESA 2001 (ESA 2001)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2161))

Included in the following conference series:

Abstract

Many modern applications store and process datasets much larger than the main memory of even state-of-the-art high-end machines. Thus massive and dynamically changing datasets often need to be stored in data structures on external storage devices, and in such cases the Input/Output (or I/O) communication between internal and external memory can become a major performance bottleneck. In this paper we survey recent advances in the development of worst-case I/O-efficient external memory data structures.

Supported in part by the National Science Foundation through ESS grant EIA-9870734, RI grant EIA-9972879, and CAREER grant EIA-9984099.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. D. J. Abel and D. M. Mark. A comparative analysis of some two-dimensional orderings. Intl. J. Geographic Informations Systems, 4(1):21–31, 1990.

    Article  Google Scholar 

  2. J. Abello, A. L. Buchsbaum, and J. R. Westbrook. A functional approach to external graph algorithms. In Proc. Annual European Symposium on Algorithms, LNCS 1461, pages 332–343, 1998.

    Google Scholar 

  3. P. K. Agarwal, L. Arge, G. S. Brodal, and J. S. Vitter. I/O-efficient dynamic point location in monotone planar subdivisions. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 1116–1127, 1999.

    Google Scholar 

  4. P. K. Agarwal, L. Arge, and J. Erickson. Indexing moving points. In Proc. ACM Symp. Principles of Database Systems, pages 175–186, 2000.

    Google Scholar 

  5. P. K. Agarwal, L. Arge, J. Erickson, P. Franciosa, and J. Vitter. Efficient searching with linear constraints. Journal of Computer and System Sciences, 61(2):194–216, 2000.

    Article  MATH  MathSciNet  Google Scholar 

  6. P. K. Agarwal, L. Arge, and S. Govindarajan. CRB-tree: An optimal indexing scheme for 2d aggregate queries. Manuscript, 2001.

    Google Scholar 

  7. P. K. Agarwal, L. Arge, T. M. Murali, K. Varadarajan, and J. S. Vitter. I/O-efficient algorithms for contour line extraction and planar graph blocking. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 117–126, 1998.

    Google Scholar 

  8. P. K. Agarwal, L. Arge, O. Procopiuc, and J. S. Vitter. Dynamic kd-trees on large data sets. Manuscript, 2001.

    Google Scholar 

  9. P. K. Agarwal, L. Arge, O. Procopiuc, and J. S. Vitter. A framework for index bulk loading and dynamization. In Proc. Annual International Colloquium on Automata, Languages, and Programming, 2001.

    Google Scholar 

  10. P. K. Agarwal, L. Arge, and J. Vahrenhold. A time responsive indexing scheme for moving points. In Proc. Workshop on Algorithms and Data Structures, 2001.

    Google Scholar 

  11. P. K. Agarwal, M. de Berg, J. Gudmundsson, M. Hammer, and H. J. Haverkort. Box-trees and R-trees with near-optimal query time. In Proc. ACM Symp. on Computational Geometry, pages 124–133, 2001.

    Google Scholar 

  12. P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry, volume 223 of Contemporary Mathematics, pages 1–56. American Mathematical Society, Providence, RI, 1999.

    Google Scholar 

  13. A. Aggarwal and J. S. Vitter. The Input/Output complexity of sorting and related problems. Communications of the ACM, 31(9):1116–1127, 1988.

    Article  MathSciNet  Google Scholar 

  14. L. Arge. The buffer tree: A new technique for optimal I/O-algorithms. In Proc. Workshop on Algorithms and Data Structures, LNCS 955, pages 334–345, 1995. A complete version appears as BRICS technical report RS-96-28, University of Aarhus.

    Google Scholar 

  15. L. Arge. The I/O-complexity of ordered binary-decision diagram manipulation. In Proc. Int. Symp. on Algorithms and Computation, LNCS 1004, pages 82–91, 1995. A complete version appears as BRICS technical report RS-96-29, University of Aarhus.

    Chapter  Google Scholar 

  16. L. Arge. External memory data structures. In J. Abello, P. M. Pardalos, and M. G. C. Resende, editors, Handbook of Massive Data Sets. Kluwer Academic Publishers, 2001. (To appear).

    Google Scholar 

  17. L. Arge, R. Barve, O. Procopiuc, L. Toma, D. E. Vengroff, and R. Wickremesinghe. TPIE User Manual and Reference (edition 0.9.01a). Duke University, 1999. The manual and software distribution are available on the web at http://www.cs.duke.edu/TPIE/.

  18. L. Arge, G. S. Brodal, and L. Toma. On external memory MST, SSSP and multi-way planar graph separation. In Proc. Scandinavian Workshop on Algorithms Theory, LNCS 1851, pages 433–447, 2000.

    Google Scholar 

  19. L. Arge, J. Chase, P. Halpin, L. Toma, D. Urban, J. Vitter, and R. Wick-remesinghe. Flow computation on massive grids. In 16’th Annual Symposium of the International Association of Landscape Ecology (US-IALE 2001), 2001.

    Google Scholar 

  20. L. Arge, P. Ferragina, R. Grossi, and J. Vitter. On sorting strings in external memory. In Proc. ACM Symp. on Theory of Computation, pages 540–548, 1997.

    Google Scholar 

  21. L. Arge, K. H. Hinrichs, J. Vahrenhold, and J. S. Vitter. Efficient bulk operations on dynamic R-trees. In Proc. Workshop on Algorithm Engineering, LNCS 1619, pages 328–347, 1999.

    Google Scholar 

  22. L. Arge, U. Meyer, L. Toma, and N. Zeh. On external-memory planar depth first search. In Proc. Workshop on Algorithms and Data Structures, 2001.

    Google Scholar 

  23. L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, J. Vahrenhold, and J. S. Vitter. A unified approach for indexed and non-indexed spatial joins. In Proc. Conference on Extending Database Technology, 1999.

    Google Scholar 

  24. L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. S. Vitter. Scalable sweeping-based spatial join. In Proc. International Conf. on Very Large Databases, 1998.

    Google Scholar 

  25. L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. S. Vitter. Theory and practice of I/O-efficient algorithms for multidimensional batched searching problems. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 685–694, 1998.

    Google Scholar 

  26. L. Arge, V. Samoladas, and J. S. Vitter. On two-dimensional indexability and optimal range search indexing. In Proc. ACM Symp. Principles of Database Systems, pages 346–357, 1999.

    Google Scholar 

  27. L. Arge, L. Toma, and J. S. Vitter. I/O-efficient algorithms for problems on grid-based terrains. In Proc. Workshop on Algorithm Engineering and Experimentation, 2000.

    Google Scholar 

  28. L. Arge and J. Vahrenhold. I/O-efficient dynamic planar point location. In Proc. ACM Symp. on Computational Geometry, pages 191–200, 2000.

    Google Scholar 

  29. L. Arge, D. E. Vengroff, and J. S. Vitter. External-memory algorithms for processing line segments in geographic information systems. In Proc. Annual European Symposium on Algorithms, LNCS 979, pages 295–310, 1995. To appear in special issues of Algorithmica on Geographical Information Systems.

    Google Scholar 

  30. L. Arge and J. S. Vitter. Optimal dynamic interval management in external memory. In Proc. IEEE Symp. on Foundations of Comp. Sci., pages 560–569, 1996.

    Google Scholar 

  31. S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Wu. An optimal algorithm for approximate nearest neighbor searching. In Proc. 5th ACM-SIAM Sympos. Discrete Algorithms, pages 573–582, 1994.

    Google Scholar 

  32. T. Asano, D. Ranjan, T. Roos, E. Welzl, and P. Widmayer. Space-filling curves and their use in the design of geometric data structures. Theoret. Comput. Sci., 181(1):3–15, July 1997.

    Google Scholar 

  33. J. Basch, L. J. Guibas, and J. Hershberger. Data structures for mobile data. Journal of Algorithms, 31(1):1–28, 1999.

    Article  MATH  MathSciNet  Google Scholar 

  34. H. Baumgarten, H. Jung, and K. Mehlhorn. Dynamic point location in general subdivisions. Journal of Algorithms, 17:342–380, 1994.

    Article  MATH  MathSciNet  Google Scholar 

  35. R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173–189, 1972.

    Article  Google Scholar 

  36. B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer. An asymptotically optimal multiversion B-tree. VLDB Journal, 5(4):264–275, 1996.

    Article  Google Scholar 

  37. N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An efficient and robust access method for points and rectangles. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 322–331, 1990.

    Google Scholar 

  38. M. A. Bender, E. D. Demaine, and M. Farach-Colton. Cache-oblivious B-trees. In Proc. IEEE Symp. on Foundations of Comp. Sci., pages 339–409, 2000.

    Google Scholar 

  39. J. L. Bentley. Decomposable searching problems. Information Processing Letters, 8(5):244–251, 1979.

    Article  MATH  MathSciNet  Google Scholar 

  40. S. Berchtold, C. Böhm, and H.-P. Kriegel. Improving the query performance of high-dimensional index structures by bulk load operations. In Proc. Conference on Extending Database Technology, LNCS 1377, pages 216–230, 1998.

    Google Scholar 

  41. S. Berchtold, B. Ertl, D. A. Keim, H.-P. Kriegel, and T. Seidl. Fast nearest neighbor search in high-dimensional spaces. In Proc. IEEE International Conference on Data Engineering, pages 209–218, 1998.

    Google Scholar 

  42. S. N. Bespamyatnikh. An optimal algorithm for closets pair maintenance. Discrete and Computational Geometry, 19:175–195, 1998.

    Article  MATH  MathSciNet  Google Scholar 

  43. G. Blankenagel and R. H. Güting. XP-trees—External priority search trees. Technical report, FernUniversität Hagen, Informatik-Bericht Nr. 92, 1990.

    Google Scholar 

  44. K. Brengel, A. Crauser, P. Ferragina, and U. Meyer. An experimental study of priority queues in external memory. In Proc. Workshop on Algorithm Engineering, LNCS 1668, pages 345–358, 1999.

    Google Scholar 

  45. G. S. Brodal and J. Katajainen. Worst-case efficient external-memory priority queues. In Proc. Scandinavian Workshop on Algorithms Theory, LNCS 1432, pages 107–118, 1998.

    Google Scholar 

  46. A. L. Buchsbaum, M. Goldwasser, S. Venkatasubramanian, and J. R. Westbrook. On external memory graph traversal. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 859–860, 2000.

    Google Scholar 

  47. P. Callahan, M. T. Goodrich, and K. Ramaiyer. Topology B-trees and their applications. In Proc. Workshop on Algorithms and Data Structures, LNCS 955, pages 381–392, 1995.

    Google Scholar 

  48. P. B. Callahan and S. R. Kosaraju. Algorithms for dynamic closest-pair and n-body potential fields. In Proc. 6th ACM-SIAM Sympos. Discrete Algorithms, pages 263–272, 1995.

    Google Scholar 

  49. P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM, 42(1):67–90, 1995.

    Article  MATH  MathSciNet  Google Scholar 

  50. T. M. Chan. Random sampling, halfspace range reporting, and construction of (≤k)-levels in three dimensions. SIAM Journal of Computing, 30(2):561–575, 2000.

    Article  MATH  Google Scholar 

  51. B. Chazelle. Filtering search: a new approach to query-answering. SIAM J. Comput., 15(3):703–724, 1986.

    Article  MATH  MathSciNet  Google Scholar 

  52. B. Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput., 17(3):427–462, June 1988.

    Google Scholar 

  53. B. Chazelle. Lower bounds for orthogonal range searching: I. the reporting case. Journal of the ACM, 37(2):200–212, Apr. 1990.

    Google Scholar 

  54. B. Chazelle and L. J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1:133–162, 1986.

    Article  MATH  MathSciNet  Google Scholar 

  55. B. Chazelle, L. J. Guibas, and D. T. Lee. The power of geometric duality. BIT, 25(1):76–90, 1985.

    Article  MATH  MathSciNet  Google Scholar 

  56. S. W. Cheng and R. Janardan. New results on dynamic planar point location. SIAM J. Comput., 21(5):972–999, 1992.

    Article  MATH  MathSciNet  Google Scholar 

  57. Y.-J. Chiang. Dynamic and I/O-Efficient Algorithms for Computational Geometry and Graph Problems: Theoretical and Experimental Results. PhD thesis, Brown University, August 1995.

    Google Scholar 

  58. Y.-J. Chiang. Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep. In Proc. Workshop on Algorithms and Data Structures, LNCS 955, pages 346–357, 1995.

    Google Scholar 

  59. Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter. External-memory graph algorithms. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 139–149, 1995.

    Google Scholar 

  60. Y.-J. Chiang and C. T. Silva. I/O optimal isosurface extraction. In Proc. IEEE Visualization, pages 293–300, 1997.

    Google Scholar 

  61. Y.-J. Chiang and C. T. Silva. External memory techniques for isosurface extraction in scientific visualization. In J. Abello and J. S. Vitter, editors, External memory algorithms and visualization, pages 247–277. American Mathematical Society, DIMACS series in Discrete Mathematics and Theoretical Computer Science, 1999.

    Google Scholar 

  62. Y.-J. Chiang, C. T. Silva, and W. J. Schroeder. Interactive out-of-core isosurface extraction. In Proc. IEEE Visualization, pages 167–174, 1998.

    Google Scholar 

  63. D. Comer. The ubiquitous B-tree. A CM Computing Surveys, 11(2):121–137, 1979.

    Article  MATH  Google Scholar 

  64. A. Crauser and P. Ferragina. On constructing suffix arrays in external memory. In Proc. Annual European Symposium on Algorithms, LNCS, 1643, pages 224–235, 1999.

    Google Scholar 

  65. A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer, and E. Ramos. Randomized external-memory algorithms for some geometric problems. In Proc. ACM Symp. on Computational Geometry, pages 259–268, 1998.

    Google Scholar 

  66. A. Crauser and K. Mehlhorn. LEDA-SM: A Platform for Secondary Memory Computation. Max-Planck-Institut für Informatik, 1999. The manual and software distribution are available on the web at http://www.mpi-sb.mpg.de/crauser/leda-sm.html.

  67. A. Crauser and K. Mehlhorn. LEDA-SM: Extending LEDA to secondary memory. In Proc. Workshop on Algorithm Engineering, 1999.

    Google Scholar 

  68. M. de Berg, J. Gudmundsson, M. Hammar, and M. Overmars. On R-trees with low stabbing number. In Proc. Annual European Symposium on Algorithms, pages 167–178, 2000.

    Google Scholar 

  69. D. J. De Witt, N. Kabra, J. Luo, J. M. Patel, and J.-B. Yu. Client-server paradise. In Proc. International Conf. on Very Large Databases, pages 558–569, 1994.

    Google Scholar 

  70. J. R. Driscoll, N. Sarnak, D. D. Sleator, and R. Tarjan. Making data structures persistent. Journal of Computer and System Sciences, 38:86–124, 1989.

    Article  MATH  MathSciNet  Google Scholar 

  71. H. Edelsbrunner. A new approach to rectangle intersections, part I. Int. J. Computer Mathematics, 13:209–219, 1983.

    Article  MATH  MathSciNet  Google Scholar 

  72. H. Edelsbrunner. A new approach to rectangle intersections, part II. Int. J. Computer Mathematics, 13:221–229, 1983.

    Article  MATH  MathSciNet  Google Scholar 

  73. H. Edelsbrunner and M. Overmars. Batched dynamic solutions to decomposable searching problems. Journal of Algorithms, 6:515–542, 1985.

    Article  MATH  MathSciNet  Google Scholar 

  74. H. Edelsbrunner and M. H. Overmars. On the equivalence of some rectangle problems. Inform. Process. Lett., 14:124–127, 1982.

    Article  MATH  MathSciNet  Google Scholar 

  75. G. Evangelidis, D. Lomet, and B. Salzberg. The hb π-tree: A multi-attribute index supporting concurrency, recovery and node consolidation. The VLDB Journal, 6(1):1–25, 1997.

    Article  Google Scholar 

  76. R. Fadel, K. V. Jakobsen, J. Katajainen, and J. Teuhola. Heaps and heapsort on secondary storage. Theoretical Computer Science, 220(2):345–362, 1999.

    Article  MATH  MathSciNet  Google Scholar 

  77. M. Farach, P. Ferragina, and S. Muthukrishnan. Overcoming the memory bottleneck in suffix tree construction. In Proc. IEEE Symp. on Foundations of Comp. Sci., pages 174–183, 1998.

    Google Scholar 

  78. P. Ferragina and R. Grossi. A fully-dynamic data structure for external substring search. In Proc. ACM Symp. on Theory of Computation, pages 693–702, 1995.

    Google Scholar 

  79. P. Ferragina and R. Grossi. Fast string searching in secondary storage: Theoretical developments and experimental results. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 373–382, 1996.

    Google Scholar 

  80. P. Ferragina and F. Luccio. Dynamic dictionary matching in external memory. Information and Computation, 146(2):85–99, 1998.

    Article  MATH  MathSciNet  Google Scholar 

  81. E. Feuerstein and A. Marchetti-Spaccamela. Memory paging for connectivity and path problems in graphs. In Proc. Int. Symp. on Algorithms and Computation, LNCS 762, pages 416–425, 1993.

    Google Scholar 

  82. P. Franciosa and M. Talamo. Time optimal halfplane search on external memory. Unpublished manuscript, 1997.

    Google Scholar 

  83. P. G. Franciosa and M. Talamo. Orders, k-sets and fast halfplane search on paged memory. In Proc. Workshop on Orders, Algorithms and Applications (ORDAL’94), LNCS 831, pages 117–127, 1994.

    Chapter  Google Scholar 

  84. G. N. Frederickson. A structure for dynamically maintaining rooted trees. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 175–184, 1993.

    Google Scholar 

  85. V. Gaede and O. Günther. Multidimensional access methods. ACM Computing Surveys, 30(2):170–231, 1998.

    Article  Google Scholar 

  86. M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter. External-memory computational geometry. In Proc. IEEE Symp. on Foundations of Comp. Sci., pages 714–723, 1993.

    Google Scholar 

  87. S. Govindarajan, T. Lukovszki, A. Maheshwari, and N. Zeh. I/O-efficient well-separated pair decomposition and its applications. In Proc. Annual European Symposium on Algorithms, pages 220–231, 2000.

    Google Scholar 

  88. D. Greene. An implementation and performance analysis of spatial data access methods. In Proc. IEEE International Conference on Data Engineering, pages 606–615, 1989.

    Google Scholar 

  89. R. Grossi and G. F. Italiano. Efficient cross-tree for external memory. In J. Abello and J. S. Vitter, editors, External Memory Algorithms and Visualization, pages 87–106. American Mathematical Society, DIMACS series in Discrete Mathematics and Theoretical Computer Science, 1999. Revised version available at ftp://ftp.di.unipi.it/pub/techreports/TR-00-16.ps.Z.

  90. R. Grossi and G. F. Italiano. Efficient splitting and merging algorithms for order decomposable problems. Information and Computation, 154(1):1–33, 1999.

    Article  MATH  MathSciNet  Google Scholar 

  91. O. Günther. The design of the cell tree: An object-oriented index structure for geometric databases. In Proc. IEEE International Conference on Data Engineering, pages 598–605, 1989.

    Google Scholar 

  92. A. Guttman. R-trees: A dynamic index structure for spatial searching. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 47–57, 1984.

    Google Scholar 

  93. J. M. Hellerstein, E. Koutsoupias, and C. H. Papadimitriou. On the analysis of indexing schemes. In Proc. ACM Symp. Principles of Database Systems, pages 249–256, 1997.

    Google Scholar 

  94. K. H. Hinrichs. The grid file system: Implementation and case studies of applications. PhD thesis, Dept. Information Science, ETH, Zürich, 1985.

    Google Scholar 

  95. S. Huddleston and K. Mehlhorn. A new data structure for representing sorted lists. Acta Informatica, 17:157–184, 1982.

    Article  MATH  MathSciNet  Google Scholar 

  96. D. Hutchinson, A. Maheshwari, J.-R. Sack, and R. Velicescu. Early experiences in implementing the buffer tree. In Proc. Workshop on Algorithm Engineering, pages 92–103, 1997.

    Google Scholar 

  97. D. Hutchinson, A. Maheshwari, and N. Zeh. An external-memory data structure for shortest path queries. In Proc. Annual Combinatorics and Computing Conference, LNCS 1627, pages 51–60, 1999.

    Chapter  Google Scholar 

  98. C. Icking, R. Klein, and T. Ottmann. Priority search trees in secondary memory. In Proc. Graph-Theoretic Concepts in Computer Science, LNCS 314, pages 84–93, 1987.

    Google Scholar 

  99. I. Kamel and C. Faloutsos. On packing R-trees. In Proc. International Conference on Information and Knowledge Management, pages 490–499, 1993.

    Google Scholar 

  100. I. Kamel and C. Faloutsos. Hilbert R-tree: An improved R-tree using fractals. In Proc. International Conf. on Very Large Databases, pages 500–509, 1994.

    Google Scholar 

  101. P. C. Kanellakis, S. Ramaswamy, D. E. Vengroff, and J. S. Vitter. Indexing for data models with constraints and classes. Journal of Computer and System Sciences, 52(3):589–612, 1996.

    Article  MATH  MathSciNet  Google Scholar 

  102. K. V. R. Kanth and A. K. Singh. Optimal dynamic range searching in non-replicating index structures. In Proc. International Conference on Database Theory, LNCS 1540, pages 257–276, 1999.

    Google Scholar 

  103. N. Katayama and S. Satoh. The SR-tree: An index structure for high-dimensional nearest-neighbor queries. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 369–380, 1997.

    Google Scholar 

  104. D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, Reading MA, second edition, 1998.

    Google Scholar 

  105. G. Kollios, D. Gunopulos, and V. J. Tsotras. On indexing mobile objects. In Proc. ACM Symp. Principles of Database Systems, pages 261–272, 1999.

    Google Scholar 

  106. E. Koutsoupias and D. S. Taylor. Tight bounds for 2-dimensional indexing schemes. In Proc. ACM Symp. Principles of Database Systems, pages 52–58, 1998.

    Google Scholar 

  107. V. Kumar and E. Schwabe. Improved algorithms and data structures for solving graph problems in external memory. In Proc. IEEE Symp. on Parallel and Distributed Processing, pages 169–177, 1996.

    Google Scholar 

  108. S. T. Leutenegger, M. A. López, and J. Edgington. STR: A simple and efficient algorithm for R-tree packing. In Proc. IEEE International Conference on Data Engineering, pages 497–506, 1996.

    Google Scholar 

  109. D. Lomet and B. Salzberg. The hB-tree: A multiattribute indexing method with good guaranteed performance. ACM Transactions on Database Systems, 15(4):625–658, 1990.

    Article  Google Scholar 

  110. A. Maheshwari and N. Zeh. External memory algorithms for outerplanar graphs. In Proc. Int. Symp. on Algorithms and Computation, LNCS 1741, pages 307–316, 1999.

    Chapter  Google Scholar 

  111. A. Maheshwari and N. Zeh. I/O-efficient algorithms for graphs of bounded treewidth. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 89–90, 2001.

    Google Scholar 

  112. J. Matouŝek. Efficient partition trees. Discrete Comput. Geom., 8:315–334, 1992.

    Article  MathSciNet  MATH  Google Scholar 

  113. E. McCreight. Priority search trees. SIAM Journal of Computing, 14(2):257–276, 1985.

    Article  MATH  MathSciNet  Google Scholar 

  114. K. Mehlhorn and S. Näher. Dynamic fractional cascading. Algorithmica, 5:215–241, 1990.

    Article  MATH  MathSciNet  Google Scholar 

  115. K. Mehlhorn and S. Näher. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge, UK, 2000.

    Google Scholar 

  116. U. Meyer. External memory bfs on undirected graphs with bounded degree. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 87–88, 2001.

    Google Scholar 

  117. D. R. Morrison. PATRICIA: Practical algorithm to retrieve information coded in alphanumeric. Journal of the ACM, 15:514–534, 1968.

    Article  Google Scholar 

  118. K. Munagala and A. Ranade. I/O-complexity of graph algorithm. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 687–694, 1999.

    Google Scholar 

  119. J. Nievergelt, H. Hinterberger, and K. Sevcik. The grid file: An adaptable, symmetric multikey file structure. ACM Transactions on Database Systems, 9(1):38–71, 1984.

    Article  Google Scholar 

  120. J. Nievergelt and E. M. Reingold. Binary search tree of bounded balance. SIAM Journal of Computing, 2(1):33–43, 1973.

    Article  MATH  MathSciNet  Google Scholar 

  121. J. Nievergelt and P. Widmayer. Spatial data structures: Concepts and design choices. In M. van Kreveld, J. Nievergelt, T. Roos, and P. Widmayer, editors, Algorithmic Foundations of GIS, pages 153–197. Springer-Verlag, LNCS 1340, 1997.

    Google Scholar 

  122. M. H. Nodine, M. T. Goodrich, and J. S. Vitter. Blocking for external graph searching. Algorithmica, 16(2):181–214, 1996.

    Article  MATH  MathSciNet  Google Scholar 

  123. J. Orenstein. Spatial query processing in an object-oriented database system. In Proc. ACM SIGMOD Conf. on Management of Data, pages 326–336, 1986.

    Google Scholar 

  124. J. Orenstein. A comparison of spatial query processing techniques for native and parameter spaces. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 343–352, 1990.

    Google Scholar 

  125. M. H. Overmars. The Design of Dynamic Data Structures Springer-Verlag, LNCS 156, 1983.

    MATH  Google Scholar 

  126. D. Pfoser, C. S. Jensen, and Y. Theodoridis. Novel approaches to the indexing of moving objects trajectories. In Proc. International Conf. on Very Large Databases, pages 395–406, 2000.

    Google Scholar 

  127. S. Ramaswamy and S. Subramanian. Path caching: A technique for optimal external searching. In Proc. ACM Symp. Principles of Database Systems, pages 25–35, 1994.

    Google Scholar 

  128. J. Robinson. The K-D-B tree: A search structure for large multidimensional dynamic indexes. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 10–18, 1981.

    Google Scholar 

  129. N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 71–79, 1995.

    Google Scholar 

  130. N. Roussopoulos and D. Leifker. Direct spatial search on pictorial databases using packed R-trees. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 17–31, 1985.

    Google Scholar 

  131. C. Ruemmler and J. Wilkes. An introduction to disk drive modeling. IEEE Computer, 27(3):17–28, 1994.

    Google Scholar 

  132. B. Salzberg and V. J. Tsotras. A comparison of access methods for time evolving data. ACM Computing Surveys, 31(2):158–221, 1999.

    Article  Google Scholar 

  133. H. Samet. Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. Addison Wesley, MA, 1990.

    Google Scholar 

  134. H. Samet. The Design and Analyses of Spatial Data Structures. Addison Wesley, MA, 1990.

    Google Scholar 

  135. V. Samoladas and D. Miranker. A lower bound theorem for indexing schemes and its application to multidimensional range queries. In Proc. ACM Symp. Principles of Database Systems, pages 44–51, 1998.

    Google Scholar 

  136. P. Sanders. Fast priority queues for cached memory. In Proc. Workshop on Algorithm Engineering and Experimentation, LNCS 1619, pages 312–327, 1999.

    Chapter  Google Scholar 

  137. N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Communications of the ACM, 29:669–679, 1986.

    Article  MathSciNet  Google Scholar 

  138. B. Seeger and H.-P. Kriegel. The buddy-tree: An efficient and robust access method for spatial data base systems. In Proc. International Conf. on Very Large Databases, pages 590–601, 1990.

    Google Scholar 

  139. T. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-tree: A dynamic index for multi-dimensional objects. In Proc. International Conf. on Very Large Databases, pages 507–518, 1987.

    Google Scholar 

  140. J. Snoeyink. Point location. In J. E. Goodman and J. O’Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 30, pages 559–574. CRC Press LLC, Boca Raton, FL, 1997.

    Google Scholar 

  141. S. Subramanian and S. Ramaswamy. The P-range tree: A new data structure for range searching in secondary memory. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 378–387, 1995.

    Google Scholar 

  142. J. D. Ullman and M. Yannakakis. The input/output complexity of transitive closure. Annals of Mathematics and Artificial Intellegence, 3:331–360, 1991.

    Article  MATH  MathSciNet  Google Scholar 

  143. J. Vahrenhold and K. H. Hinrichs. Planar point-location for large data sets: To seek or not to seek. In Proc. Workshop on Algorithm Engineering, 2000.

    Google Scholar 

  144. J. van den Bercken, B. Seeger, and P. Widmayer. A generic approach to bulk loading multidimensional index structures. In Proc. International Conf. on Very Large Databases, pages 406–415, 1997.

    Google Scholar 

  145. J. van den Bercken, B. Seeger, and P. Widmayer. A generic approach to processing non-equijoins. Technical Report 14, Philipps-Universität Marburg, Fachbereich Matematik und Informatik, 1998.

    Google Scholar 

  146. M. J. van Kreveld and M. H. Overmars. Divided k-d trees. Algorithmica, 6:840–858, 1991.

    Article  MATH  MathSciNet  Google Scholar 

  147. P. J. Varman and R. M. Verma. An efficient multiversion access structure. IEEE Transactions on Knowledge and Data Engineering, 9(3):391–409, 1997.

    Article  Google Scholar 

  148. D. E. Vengroff. A transparent parallel I/O environment. In Proc. DAGS Symposium on Parallel Computation, 1994.

    Google Scholar 

  149. D. E. Vengroff and J. S. Vitter. Efficient 3-D range searching in external memory. In Proc. ACM Symp. on Theory of Computation, pages 192–201, 1996.

    Google Scholar 

  150. D. E. Vengroff and J. S. Vitter. I/O-efficient scientific computation using TPIE. In Proceedings of the Goddard Conference on Mass Storage Systems and Technologies, NASA Conference Publication 3340, Volume II, pages 553–570, 1996.

    Google Scholar 

  151. J. S. Vitter. External memory algorithms and data structures. In J. Abello and J. S. Vitter, editors, External Memory Algorithms and Visualization, pages 1–38. American Mathematical Society, DIMACS series in Discrete Mathematics and Theoretical Computer Science, 1999.

    Google Scholar 

  152. J. S. Vitter. Online data structures in external memory. In Proc. Annual International Colloquium on Automata, Languages, and Programming, LNCS 1644, pages 119–133, 1999.

    Chapter  Google Scholar 

  153. J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory, I: Two-level memories. Algorithmica, 12(2–3):110–147, 1994.

    Article  MATH  MathSciNet  Google Scholar 

  154. S. Saltenis, C. S. Jensen, S. T. Leutenegger, and M. A. López. Indexing the positions of continuously moving objects. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 331–342, 2000.

    Google Scholar 

  155. O. Wolfson, A. P. Sistla, S. Chamberlain, and Y. Yesha. Updating and querying databases that track mobile units. Distributed and Parallel Databases, 7(3):257–287, 1999.

    Article  Google Scholar 

  156. N. Zeh. I/O-efficient planar separators and applications. Manuscript, 2001.

    Google Scholar 

  157. D. Zhang, A. Markowetz, V. Tsotras, D. Gunopulos, and B. Seeger. Efficient computation of temporal aggregates with range predicates. In Proc. ACM Symp. Principles of Database Systems, pages 237–245, 2001.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Duke University, Durham, NC, 27708, USA

    Lars Arge

Authors
  1. Lars Arge
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Mathematics and Computer Science and Heinz Nixdorf Institute, Paderborn University, 33095, Paderborn, Germany

    Friedhelm Meyer auf der Heide

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Arge, L. (2001). External Memory Data Structures. In: auf der Heide, F.M. (eds) Algorithms — ESA 2001. ESA 2001. Lecture Notes in Computer Science, vol 2161. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44676-1_1

Download citation

  • DOI: https://doi.org/10.1007/3-540-44676-1_1

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-42493-2

  • Online ISBN: 978-3-540-44676-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation