HP Labs Technical Reports

Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data

Kolovson, Curtis; Stonebraker, Michael

HPL-91-55

Keyword(s):

Abstract: We propose new indexing techniques for interval data in K (greater than or equal to) 1 dimensions consisting of a set of extensions to a class of database indexing structures. These techniques are useful for improving index search performance for spatial data composed of multi-dimensional intervals that have non-uniform length distributions. Interval data collections having non-uniform length distributions are likely to occur in practice, and may be typical of historical data collections in which tuples represent intervals in the time dimension. We present these indexing techniques, illustrate how they may be applied to the R-Tree index, and provide the results of performance experiments.

Back to Index