An integrated index structure for object-oriented and spatio-temporal information systems

An index structure is one of the access methods extensively utilized in the data- base area. It defines how access to the data stored in pages on disk is made by permit- ting the retrieval of stored objects through a defined key, that is an attribute of the object. A multi-dimensional (dD) index defines several attributes non-concatenated as its key. This work is devoted to the study of a range of multi-dimensional access methods that could solve the problem of retrieving spatio-temporal objects in object-oriented database applications. The study of some performance parameters and the comparison of five extensions to the selected index method is also included. After presenting a comparison between several dD indexing methods, the R tree structure was selected to index spatio-temporal objects by treating homogeneously both spatial and temporal dimensions. An object-oriented development technique named TDSO was utilized to specify and design the RTree class extensions and the OTree class, which were implemented in C++.

A novel approach to building dD indexes which attempts to improve the hit ratio by accommodating spatio-temporal search operators within the indexing mechanism is the first contribution. The development of a family of methods for indexing into dD spatio-temporal data together with preliminary testing of these techniques is the second contribution of the work. We also show a substantial improvement in terms of reduction in wasted space through a redistribution policy and the achievement of better hit ratios and fewer disk accesses in some range searches. In general, we have provided support for the usefulness of the TDSO and object-oriented techniques, which led to a very flexible scheme whereby the indexing structure was easily adapted to our problem.