A General Solution of the n-dimensional B-tree Problem

Michael Freeston

European Computer-Industry Research Centre (ECRC)
Arabellastraße 17
D-81925 München


This talk presents a general solution of the n-dimensional B-tree problem, and discusses its implications for present and future generations of database and knowledge base systems.

The n-dimensional B-tree problem has been outstanding for 25 years, and has been described as "one of the persistent puzzles of computer science". The solution we present is surprisingly simple, and of such generic nature that it opens up a flood of possible application areas: multi-dimensional indexing in conventional database applications; spatial object indexing in GIS; image indexing in digital libraries; and scalable rule indexing in deductive databases.

For example, until now, not a single design for a dynamic spatial object index has been able to meet the predictable and controllable worst-case characteristics of the B-tree. We show how this can now be achieved.

More generally, we show how the result makes it possible to index any complex objects whose structures can be expressed as trees.

For a postscript version of this abstract, click here.