Revised version of ``Efficient Cross-Trees for External Memory''

Due to a printing problem, the revised version of our paper (Efficient cross-trees for external memory, in ``External Memory Algorithms and Visualization'', James Abello and Jeffrey Scott Vitter eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society Press, Providence, RI, 1999) has been replaced by the (shorter) submitted version. In this technical report, we include the revised version that has not been published by mistake. In particular, we describe efficient methods for organizing and maintaining large multidimensional data sets in external memory. This is particular important as access to external memory is currently several order of magnitudes slower than access to main memory, and current technology advances are likely to make this gap even wider. We focus particularly on multidimensional data sets which must be kept simultaneously sorted under several total orderings: these orderings may be defined by the user, and may also be changed dynamically by the user throughout the lifetime of the data structures, according to the application at hand. Besides standard insertions and deletions of data, our proposed solution can perform efficiently {\em split\/} and {\em concatenate\/} operations on the whole data sets according to any ordering. This allows the user: (1)~to dynamically rearrange any ordering of a segment of data, in a time that is faster than recomputing the new ordering from scratch; (2)~to efficiently answer queries related to the data contained in a particular range of the current orderings. Our solution fully generalizes the notion of B-trees to higher dimensions by carefully combining space-driven and data-driven partitions. Balancing is easy as we introduce a new multidimensional data structure, {\em the cross-tree}, that is the cross product of balanced trees. As a result, the cross-tree is competitive with other popular index data structures that require linear space (including k-d trees, quad-trees, grid files, space filling curves, hB-trees, and R-trees).