I/o-efficient algorithms for processing massive spatial data
Pankaj K. Agarwal, Ke Yi · 2006
Data management is a central problem in this modern age with exploding information. The huge volume of data that is being generated on a daily basis makes the problem even more challenging, and scalability is essential for the algorithms that handle these massive data sets. Traditionally, algorithms are studied in the familiar RAM model, where each memory cell can be accessed with uniform cost. This assumption, however, is far from reality when we face today's massive data sets that cannot fit in main memory, in which case the memory-disk communication cost, or I/O cost, becomes the bottleneck during computation. In recent years, I/O-efficient algorithms have been a successive and active direction to better scalability on massive data. Spatial data is one of the most important forms of data that are often generated in huge quantity. They can appear in a variety of applications such as spatial databases, geographical information systems, CAD, robotics, computer vision, etc. Lots of non spatial data, for example relational data, can also be interpreted as spatial data and many spatial data handling techniques can be applied. This dissertation has contributed to both the theory and practice of I/O-efficient algorithms on processing massive spatial data. Many of the algorithms developed in this thesis are both provably efficient and superior in practice. This dissertation consists of two parts. The first part is concerned with processing massive terrain data. Modern technologies, such as Laser altimetry (LIDAR), are capable of acquiring millions of georeferenced points within minutes to hours. Traditional algorithms simply do not scale to such high volumes of data, and I/O-efficient techniques becomes essential in geographical information systems (GIS) that aim at handling these data. We mainly study two issues: building a terrain model and topological analysis of the terrain. We choose to use the triangulated irregular network ( TIN) as our terrain model, and develop an I/O-efficient algorithm for constructing a TIN model from raw terrain data. To analyze the topological structure of the underlying terrain, we give new I/O-efficient algorithms to compute the topological persistence and the contour tree from the TIN model that has been constructed. We also implemented our algorithms, and experimental results show that our new algorithms give order-of-magnitude improvement over previous internal memory algorithms. In the second part of this thesis, we consider several I/O-efficient range searching problems. Generally speaking, in a range searching problem, we want to build a disk-based data structure for a set of spatial objects, such that a certain type of queries can be answered efficiently. These data structures often serve as the backbones of many of the indexes in modern spatial databases, or even relational databases. We study three range searching problems in this thesis: range-max queries, point enclosure queries, and window queries. For all three problems, we give new theoretical results that significantly improve upon previous results. In particular, matching upper and lower bounds are presented for the point enclosure problem and window query problem. Furthermore, our new data structure for the window query problem, which is a variant of the R-tree, has been implemented and demonstrated to have excellent performance in practice as well.