There has been no significant change in the dynamic indexing methods supporting database systems since the invention of the B-tree over twenty-five years ago. And yet the whole classical approach to dynamic database indexing has long since become inappropriate and increasingly inadequate: we are moving rapidly from the conventional one-dimensional world of fixed-structure text and numbers to a multi-dimensional world of variable structures, objects and images, in space and time. This project is based on a new multi-dimensional indexing technology which rejects conventional benchmark criteria in favor of a natural principle intuitively understood by users: the more information given to guide a query, the faster the response - regardless of any particular instantiation pattern. As a result, conventional relational indexing becomes much more flexible, with some classes of query improving on average by an order of magnitude, while retaining the logarithmic storage and update characteristics of the B-tree. But the main feature of the technology is its applicability to a much wider range of data types -- from nested relations to logic clauses, and from spatial objects to pictorial images. Two specific areas show particular promise: the efficient indexing of large rule bases, and substantially improved performance of very large and mission-critical GIS (geographic information systems) applications. Digital libraries will be used as an initial focus for enhanced support and as testbeds for comparative performance evaluation.
