Storage and retrieval of multidimensional data is necessary for many scientific, geographic, engineering, and business applications. Traditional database secondary storage indexing techniques such as B-trees and hash tables are not suitable for dealing with multidimensional data, as data access is performed by concentrating on only one-dimension at a time and large quantities of extraneous data may be retrieved. The main goal of this project is to explore and develop techniques for efficient loading, retrieval, and update of large disk-resident multidimensional data for both single machine and parallel machine architectures. Storage and processing of both point and region data are considered. The database community has independently developed a number of disk-based multi-dimensional indexing schemes, without applying results from relevant fields that may significantly improve loading and retrieval performance. Accordingly, the approach used in this project is firmly grounded within the realm of computational geometry, a discipline that has produced numerous techniques for the efficient processing of memory-resident multidimensional data. The generalization and improvement of these techniques to handle efficiently disk-resident data is an important part of this research. Additionally, the use of parallelism to provide improved load and query response times for very large data sets is also considered. The resulting indexing techniques will enable higher level database architectures to provide efficient access to the very large multi-dimensional datasets of the future, thus enabling database technology to keep up with demands placed upon it from science and business as a whole.
