1. 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 

2. L. Arge. The buffer tree: A new technique for optimal I/O-algorithms. InProc. 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 

3. L. Arge.Efficient External-Memory Data Structures and Applications. PhD thesis, University of Aarhus, February/August 1996.

   Google Scholar 

4. L. Arge. External-memory algorithms with applications in geographic information systems. In M. van Kreveld, J. Nievergelt, T. Roos, and P. Widmayer, editors,Algorithmic Foundations of GIS. Springer-Verlag, LNCS 1340, 1997.

   Google Scholar 

5. L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. S. Vitter. Scalable sweeping-based spatial join. InProc. 24th Intl. Conf. on Very Large Databases, pages 570–581, 1998.

   Google Scholar 

6. 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. InProc. ACM-SIAM Symp. on Discrete Algorithms, pages 685–694, 1998.

   Google Scholar 

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

   Article  Google Scholar 

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

   Article  Google Scholar 

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

   Google Scholar 

10. S. Berchtold, C. Böhm, and H.-P. Kriegel. Improving the query performance of high-dimensional index structures by bulk load operations. InProc. Intl. Conf. on Extending Database Technology, pages 216–230, 1998.

    Google Scholar 

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

    Google Scholar 

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

    Article MATH  Google Scholar 

13. R. F. Cromp. An intellegent information fusion system for handling the archiving and querying of terabyte-sized spatial databases. InS. R. Tate ed., Report on the Workshop on Data and Image Compression Needs and Uses in the Scientific Community,CESDIS Technical Report Series, TR-93-99, pages 75–84, 1993.

    Google Scholar 

14. D. J. DeWitt, N. Kabra, J. Luo, J. M. Patel, and J.-B. Yu. Client-server paradise. InProc. 20th Intl. Conf. on Very Large Databases, pages 558–569, 1994.

    Google Scholar 

15. D. Greene. An implementation and performance analysis of spatial data access methods. InProc. IEEE Intl. Conf. on Data Engineering, pages 606–615, 1989.

    Google Scholar 

16. A. Guttman. R-trees: A dynamic index structure for spatial searching. InProc. SIGMOD Intl. Conf. on Management of Data, pages 47–57, 1985.

    Google Scholar 

17. I. Kamel and C. Faloutsos. On packing R-trees. InProc. 2nd Int. Conf. on Information and Knowledge Management (CIKM), pages 490–499, 1993.

    Google Scholar 

18. I. Kamel and C. Faloutsos. Hilbert R-tree: An improved R-tree using fractals. InProc. 20th Intl. Conf. on Very Large Databases, pages 500–509, 1994.

    Google Scholar 

19. I. Kamel, M. Khalil, and V. Kouramajian. Bulk insertion in dynamic R-trees. InProc. 4th Intl. Symp. on Spatial Data Handling, pages 3B.31–3B.42, 1996.

    Google Scholar 

20. S. T. Leutenegger, M. A. Lopez, and J. Edgington. STR: A simple and efficient algorithm for R-tree packing. InProc. IEEE International Conferance on Data Engineering, pages 497–506, 1997.

    Google Scholar 

21. 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. Springer-Verlag, LNCS 1340, 1997.

    Google Scholar 

22. J. M. Patel and D. J. DeWitt. Partition based spatial-merge join. InProc. SIG-MOD Intl. Conf. on Management of Data, pages 259–270, 1996.

    Google Scholar 

23. N. Roussopoulos, Y. Kotidis, and M. Roussopoulos. Cubetree: Organization of and bulk incremental updates on the data cube. InProc. SIGMOD Intl. Conf. on Management of Data, pages 89–111, 1997.

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

26. T. Sellis, N. Roussopoulos, and C. Faloutsos. The R⁺-tree: A dynamic index for multi-dimensional objects. InProc. 13th Int. Conf. on Very Large Databases, pages 507–518, 1987.

    Google Scholar 

27. TIGER/Line (tm). 1992 technical documentation. Technical report, U. S. Bureau of the Census, 1992.

    Google Scholar 

28. J. van den Bercken, B. Seeger, and P. Widmayer. A generic approach to bulk loading multidimensional index structures. InProc. 23rd Intl. Conf. on Very Large Databases, pages 406–415, 1997.

    Google Scholar 

29. D. E. Vengroff. A transparent parallel I/O environment. InProc. DAGS Symposium on Parallel Computation, 1994.

    Google Scholar 

30. D. E. Vengroff.TPIE User Manual and Reference. Duke University, 1997. Available via WWW athttp://www.cs.duke.edu/TPIE/.

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

    Google Scholar 

32. J. S. Vitter. External Memory Algorithms. In J. Abello and J. S. Vitter, editors,External Memory Algorithms and Visualization, DIMACS series. American Mathematical Society, to appear. Earlier shorter versions appear as an invited tutorial inProc. 17th ACM Symp. on Principles of Database Systems, pages 119–128, 1998, and as an invited paper inProc. 6th Annual European Symposium on Algorithms, pages 1–25, 1998.

    Google Scholar 

Download references