Algorithms for very large spatial databases.

摘要

In this thesis, we aim at bridging the gap between theory and practice in handling very large spatial data sets by developing I/O-efficient algorithms and data structures that are both practical and robust. We prove theoretical bounds on the performance of these techniques in the standard I/O model. We also demonstrate their practical efficiency through extensive experiments, both on real-life and synthetic data. The programs were developed using TPIE, a software package that facilitates the implementation of I/O-efficient techniques. We developed a new module of TPIE that adds support for on-line data structures.; In the first part of the thesis we develop a theoretically optimal algorithm for a large class of batched searching problems, including batched range searching, orthogonal segment intersection and rectangle intersection. By applying this algorithm to rectangle intersection, we obtain a new algorithm for the spatial join operation. We validate the practical performance, robustness and scalability of our algorithm by comparing it with the state-of-the-art algorithm from the database community.; In the second part of the thesis we study algorithms and data structures for on-line searching problems. In particular, we concentrate on the range query, the most important query type in spatial databases. We present the Bkd-tree, a new I/O-efficient dynamic data structure for answering range queries on point data sets. We present the results of an extensive experimental study showing that the Bkd-tree maintains high space utilization and excellent query and update performance regardless of the number of updates performed on it. In addition, we present a new general I/O-efficient construction (bulk loading) technique for a large class of structures. Our approach gives considerably improved construction I/O bounds for kd-trees and other existing data structures.