External-Memory Algorithms and Data Structures: General concepts and techniques

Research output: Contribution to book/anthology/report/proceedingBook chapterResearchpeer-review

  • Department of Computer Science

The data sets involved in many modern applications are often too massive to fit in main memory of even the most powerful computers and must therefore reside on disk. Thus communication between internal and external memory, and not actual computation time, becomes the bottleneck in the computation. This is due to the huge difference in access time of fast internal memory and slower external memory such as disks.

The goal of theoretical work in the area of external memory algorithms (also called I/O algorithms or out-of-core algorithms) has been to develop algorithms that minimize the Input/Output communication (or just I/O) performed when solving a given problem. The area was effectively started in the late eighties by Aggarwal and Vitter and subsequently I/O algorithms have been developed for several problem domain. Also I/O performance can often be improved if many disks can efficiently be used in parallel and the use of parallel disks has received a lot of theoretical attention. See below for recent surveys of theoretical results in the area of I/O-efficient algorithms.

TPIE is designed to bridge the gap between the theory and practice of parallel I/O systems. It is intended to demonstrate all of the following simultaneously:

Abstract away the details of how I/O is performed so that programmers need only deal with a simple high level interface.Implement I/O-optimal paradigms for large scale computation that are efficient not only in theory, but also in practice.Remain flexible, allowing programmers to specify the functional details of computation taking place within the supported paradigms. This will allow a wide variety of algorithms to be implemented within the system.Be portable across a variety hardware platforms.Be extensible, so that new features can be easily added later.TPIE is implemented as a set of templated classes and functions in C++. It also includes a small library and a set of test and sample applications.
Original languageEnglish
Title of host publicationAlgorithms and Theory of Computation Handbook (second edition)
EditorsMikhail J. Atallah, Marina Blanton
Place of publicationUSA
PublisherCRC Press
Publication year2010
ISBN (print)9781584888185, 9781584888222 (vol. 1), 9781584888208 (vol. 2)
Publication statusPublished - 2010

See relations at Aarhus University Citationformats

ID: 10560937