Many modern applications store and process datasets much larger than the main memory of even state-of-the-art high-end machines. In such cases, the Input/Output (or I/O) communication between fast internal memory and slow disks, rather than actual internal computation time, can become a major performance bottleneck. In the last decade, much attention has therefore been focused on the development of theoretically I/O-efficient algorithms and data structures.

In this talk we discuss recent efforts at Duke University to investigate the practical merits of theoretically developed I/O-efficient algorithms. We describe the goals and architecture of the {\sc TPIE} environment for efficient implementation of I/O-efficient algorithms, as well as some of the implementation projects conducted using the
environment, and discuss some of the experiences we have had and lessons we have learned in these projects. We especially discuss the {\sc TerraFlow} system for efficient flow computation on massive grid-based terrain models, developed in collaboration with environmental researchers. Finally we discuss how the implementation and experimentation work has supported educational efforts.

© Association for Computer Machinery and the Society for Industrial and Applied Mathematics 2003.