Assume that a set of objects is clustered; each object belongs to one or more clusters. The question is under which conditions the objects can be arranged linearly in such a way that each cluster consists of a consecutive section of this arrangement (this is called the consecutive retrieval property). This is already impossible for three objects with each pair forming a cluster.
The paper is mostly concerned with level clusterings defined by the restriction that no cluster be a proper subset of another cluster. An algorithm is developed which checks in linear time (linear in the sum of objects, clusters, and cluster sizes) whether a given set of objects has the consecutive retrieval property; in the positive case, a fitting arrangement is found.
If a set of objects does not have the consecutive retrieval property, one might wish to store some objects at several places such that each cluster is arranged consecutively. Even for level clusterings, the problem of finding the arrangement with minimum redundancy is shown to be NP-complete. An efficient algorithm to generate a reasonable arrangement is developed. Some special results are added for multilevel clusterings.