Foundations of Geometric and Metric Databases

摘要许多应用涉及到从数据库中存储和检索空间和度量数据。 算法和底层表示的效率是有效使用此类数据库的关键。 本研究从空间和度量数据库中涉及查询（如最近邻查找）的应用程序的角度解决了效率问题。 其目标是加快计算机图形、地理信息系统（GIS）和计算机视觉应用中使用大型数据库的操作。所考虑的应用程序包括点云模型的快速计算，以及数据的有效表示，如地形通过三角形的下垫面。 在这个项目中，我们研究了三个相关的主题。 首先是计算计算机图形学应用中点云模型的k近邻连接。 特别是，我们不是计算每个数据点的k个最近邻，而是重用我们已经执行任务的点的邻居集。 该方法是利用给定对象q的局部性的概念（例如，点、包含查询点的块或任意对象），该搜索分级结构被定义为可以包含Q的K个最近邻居的块的集合。 我们在移动对象数据库的上下文中对此进行研究，其中查询对象处于运动中，而数据库中的其余对象是静止的（例如，加油站、建筑物、餐馆等）。 目标是确定必须搜索的区域，以找到其运动被限制在特定空间区域的一个或多个对象的k个最近邻居。 我们正在设计有效的（可能是最佳的）方法来计算基于我们的增量最近邻算法的局部性。我们将探索用于计算机视觉和计算机图形学的Hausdorff距离的计算。第二是分布式空间索引在P2P网络中的应用研究。 该方法是在这样的环境中应用我们的增量最近邻算法。 我们还扩展了CHORD方法，以提供基于键的查找服务，在一个分布式的空间索引，结合更大的各种空间索引。 此外，我们还研究了基于CAN密钥的查找服务与四叉树的关系。第三是三角索引。 三角剖分通常使用存储三角形之间的拓扑关系的邻接结构的变体来表示。 查找包含查询点的实际三角形需要对三角形集合强制执行索引。 我们正在设计一个数学模型，帮助评估使用基于PM2四叉树的桶方法存储三角剖分的效率。 该模型使用几何概率。

ABSTRACTNumerous 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.