| Multidimensional index structures enable searching in spatial, image, text, audio, and video databases. Current multidimensional index structures do not scale with database size, data dimensionality, and the number of concurrent users operating on them. In this thesis, we first propose new techniques for fast searching in low-dimensional databases, such as spatial and geographic information systems, and in high-dimensional databases, such as image, audio, video and text documents. We then examine the time complexity of searching in such multidimensional databases and propose optimal index structures. We also explore other alternatives such as parallel processing to improve query performance. These techniques concentrate only on the performance of individual query or update operations. In the final portion of the thesis, we develop new concurrency control protocols to achieve high throughput in the presence of multiple users. Together, these techniques achieve scalability with the number of users, the database size, and the data dimensionality. |
