Multimedia information systems have emerged as an essential component of many application domains ranging from library information systems to entertainment technology. A challenging task when implementing these systems is to support a continuous display of multimedia objects. The challenging is due to the low I/O bandwidth of the current disk technology, the high bandwidth requirement of multimedia objects, and the large size of these objects which requires them to be almost always disk resident. One approach to resolve this limitation is to decluster a multimedia object across multiple disk drives in order to employ the aggregate bandwidth of several disks to support its continuous retrieval (and display). To provide on-line access to vast amount of data economically, the storage architecture of these systems is expected to be hierarchical.