Implementing I/O-Efficient Data Structures Using TPIE

L. Arge, O. Procopiuc, and J. S. Vitter. ``Implementing I/O-Efficient Data Structures Using TPIE,'' Proceedings of the 10th Annual European Symposium on Algorithms (ESA '02), Rome, Italy, September 2002, published in Lecture Notes in Computer Science, Springer-Verlag, 2461, Berlin, Germany, 88-100.

Full text (Adobe pdf format)

In recent years, many theoretically I/O-efficient algorithms and data structures have been developed. The TPIE project at Duke University was started to investigate the practical importance of these theoretical results. The goal of this ongoing project is to provide a portable, extensible, flexible, and easy to use C++ programming environment for efficiently implementing I/O-algorithms and data structures. The TPIE library has been developed in two phases. The first phase focused on supporting algorithms with a sequential I/O pattern, while the recently developed second phase has focused on supporting on-line I/O-efficient data structures, which exhibit a more random I/O pattern. This paper describes the design and implementation of the second phase of TPIE.