Indexing techniques for multi-dimensional spatial data and historical data in database management systems
Curtis P. Kolovson · 1991
Many database applications require the ability to manage large collections of spatial data objects, such as Geographic Information Systems. Another important class of data requiring new indexing techniques is historical data. Historical data is maintained in append-only database systems which do not overwrite or delete previous data values. Spatial and historical data are closely related because the latter may be considered a special case of the former, since attribute values may be associated with points or intervals in the time dimension. The focus of this research is on indexing techniques for providing efficient support of spatial and historical data in database management systems. The major objectives of this work are to design indexing techniques in support of (1) spatial data composed of intervals in multiple dimensions, (2) nonuniform query distributions, and (3) database archives which may span magnetic and optical disk media. Corresponding to the three objectives mentioned above, this work proposes three major approaches: Segment Indexes, Lop-Sided Indexes, and Mixed-Media Indexes. Segment Indexes are multi-way, tree-structured indexes which store records representing interval data in both the leaf and non-leaf nodes. The Segment Index approach is to store each interval in the highest level node such that the extent of the interval spans (covers) the region represented by that node and all of its descendants. Lop-Sided Indexes are multi-way, tree-structured indexes which support a specified non-uniform query distribution. Non-uniform query distributions are likely to arise in the case of historical data, for example, where queries involving the most recent data will generally occur more frequently than queries requesting older historical data. Mixed-Media Indexes are indexing structures that may span magnetic and optical disks in order to exploit the benefits of both, i.e., the high performance and rewritability of magnetic disks and the low media cost and large capacity of optical disks.