Clustering Techniques for Minimizing External Path Length

Abstract

There are a variety of main-memory access structures, such as segment trees, and quad trees, whose properties, such as good worstcase behaviour, make them attractive for database applications. Unfortunately, the structures are typically `long and skinny', whereas disk data structures must be `shortand -fat' (that is, have a high fanout and low height) in order to minimize I/O. We consider how to cluster the nodes (that is, map the nodes to disk pages) of mainmemory access structures such that although a path may traverse many nodes, it only traverses a few disk pages. The number of disk pages traversed in a path is called the external path length. We address several versions of the clustering problem. We present a clustering algorithm for tree structures that generates optimal worst-case external path length mappings; we also show how to make it dynamic, to support updates. We extend the algorithm to generate mappings that minimize the average weighted external path lengths. We also sh...