Tech Report CS-95-15

OODB Indexing by Class-Division

Sridhar Ramaswamy and Paris C. Kanellakis

May 1995


Indexing a class hierarchy, in order to efficiently search or update the objects of a class according to a (range of) value(s) of an attribute, impacts OODB performance heavily. For this indexing problem, most systems use the class hierarchy index (CH) technique of [. Kim Dale .] implemented using B+-trees. Other techniques, such as those of [. Low Ooi , hcC-tree , CG-tree .], can lead to improved average-case performance but involve the implementation of new data-structures. As a special form of external dynamic two-dimensional range searching, this OODB indexing problem is solvable within reasonable worst-case bounds [. pods93 .]. Based on this insight, we have developed a technique, called indexing by class-division (CD), which we believe can be used as a practical alternative to CH. We present an optimized implementation and experimental validation of CD's average-case performance. The main advantages of the CD technique are: (1) CD is an extension of CH that provides a significant speed-up over CH for a wide spectrum of range queries---this speed-up is at least linear in the number of classes queried for uniform data and larger otherwise; and (2) CD queries, updates and concurrent use are implementable using existing B+-tree technology. The basic idea of class-division involves a time-space tradeoff and CD requires some space and update overhead in comparison to CH. In practice, this overhead is a small factor (2 to 3) and, in worst-case, is bounded by the depth of the hierarchy and the logarithm of its size.

(complete text in pdf or gzipped postscript)