**Lars Arge**

**August 1996**

In this thesis we study the Input/Output (I/O) complexity of large-scale problems arising e.g. in the areas of database systems, geographic information systems, VLSI design systems and computer graphics, and design I/O-efficient algorithms for them.

A general theme in our
work is to design I/O-efficient algorithms through the design of
I/O-efficient data structures. One of our philosophies is to try to design
I/O algorithms from internal memory algorithms by exchanging the data
structures used in internal memory with their external memory counterparts.
The results in the thesis include a technique for transforming an internal
memory tree data structure into an external data structure which can be used
in a *batched* dynamic setting, that is, a setting where we for example
do not require that the result of a search operation is returned immediately.
Using this technique we develop batched dynamic external versions of the
(one-dimensional) range-tree and the segment-tree and we develop an external
priority queue. These structures can be used in standard internal memory
sorting algorithms and algorithms for problems involving geometric objects.
The latter has applications to VLSI design. Using the priority queue we
improve upon known I/O algorithms for fundamental graph problems, and develop
new efficient algorithms for the graph-related problem of ordered
binary-decision diagram manipulation. Ordered binary-decision diagrams are
the state-of-the-art data structure for boolean function manipulation and
they are extensively used in large-scale applications like logic circuit
verification.

Combining our batched dynamic segment tree with the novel technique of external-memory fractional cascading we develop I/O-efficient algorithms for a large number of geometric problems involving line segments in the plane, with applications to geographic informations systems. Such systems frequently handle huge amounts of spatial data and thus they require good use of external-memory techniques.

We also manage to use the ideas in the batched dynamic segment tree to develop ``on-line'' external data structures for a special case of two-dimensional range searching with applications to databases and constraint logic programming. We develop an on-line external version of the segment tree, which improves upon the previously best known such structure, and an optimal on-line external version of the interval tree. The last result settles an important open problem in databases and I/O algorithms. In order to develop these structure we use a novel balancing technique for search trees which can be regarded as weight-balancing of B-trees.

Finally, we develop a technique for transforming internal memory lower bounds to lower bounds in the I/O model, and we prove that our new ordered binary-decision diagram manipulation algorithms are asymptotically optimal among a class of algorithms that include all know manipulation algorithms.

Available as *PostScript*,
*PDF*.

BRICS WWW home page