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.