I/O-EFFICIENT ALGORITHMS

I/O-efficient algorithms are algorithms designed in a two-level external memory (or I/O-) model, where the memory hierarchy consists of a main memory of limited size M and an external memory (disk) of unlimited size; the goal is to minimize the number of times a block of B consecutive elements is read (or written) from (to) disk (an I/O-operation, or simply I/O). The model is motivated by the fact that transfers between main memory and disk, rather than, e.g., CPU computation is the bottleneck when processing massive datasets residing on disk.

Even before the center start the I/O-efficient algorithms area was quite developed. Not only had a large number of algorithms and algorithm design techniques been developed, but the immense practical importance of I/O-efficient algorithms had also been established through experimental work. Still many important problems remained open.The center considers a number of problems in the I/O-model, including a number of fundamental geometric data structure and graph traversal problems and some practically motivated terrain data processing problems. Please refer to the centers annual reports for a discussion of obtained result.