Foundations of Geometric and Metric Databases

University Of Maryland, College Park, College Park MD

Investigators

Abstract

ABSTRACT Numerous applications involve the storage and retrieval of spatial and metric data from databases. Efficiency of the algorithms and underlying representations is the key to effectively using such databases. This research addresses efficiency issues from the perspective of applications in spatial and metric databases involving queries such as nearest neighbor finding. The goal is to speed up operations that arise in applications in computer graphics, geographic information systems (GIS), and computer vision that make use of large databases. The applications that are considered include the fast computation of point cloud models as well the efficient representation of data such as terrains via triangulations of the underlying surface. The implementation of such data in a distributed environment is also studied. In this project we are investigating three related topics. First is computing k nearest neighbor joins for point cloud models in computer graphics applications. In particular, rather than computing the k nearest neighbors for each data point, we reuse the set of neighbors of the points for which we have already performed the task. The approach is to exploit the concept of locality of a given object q (e.g., a point, a block containing a query point, or an arbitrary object) in a search hierarchy defined to be the set of blocks which could contain the k nearest neighbors of q. We investigate this in the context of moving object databases where the query object is in motion while the remaining objects in the database are stationary (e.g., gas stations, buildings, restaurants, etc.). The goal is to determine the region that must be searched to find the k nearest neighbors of an object or objects whose motion is restricted to a particular region of space. We are devising efficient (possibly optimal) methods to compute the locality based on our incremental nearest neighbor algorithm. We explore computation of the Hausdorff distance that is used in computer vision and computer graphics. Second is an investigation of distributed spatial indexes for applications in P2P networks. The approach is to apply our incremental nearest neighbor algorithm in such an environment. We also extend CHORD method to provide key-based lookup service in a distributed spatial index in conjunction with a larger variety of spatial indexes. Additionally, we study the relationship of the CAN key-based lookup service to a quadtree. Third is in indexing triangulations. Triangulations are usually represented using a variant of an adjacency structure that stores the topological relations between the triangles. Finding the actual triangle that contains the query point requires the imposition of an index on the collection of triangles. We are devising a mathematical model that helps evaluate the efficiency of using a bucketing method based on the PM2 quadtree to store the triangulation. The model uses geometric probability.