Approximate UV computation based on space decomposition
Approximate UV computation based on space decomposition
复制标题
基于空间分解的近似UV计算
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Reynold Cheng
中科院分区：
文献类型：
--
作者：
Klaus Arthur Schmid;Tobias Emrich;Andreas Züfle;M. Renz;Reynold Cheng
Voronoi图通常用于回答空间数据库中传统的最近邻查询。在这项工作中，我们提出了一种新的方法来计算Voronoi细胞的情况下，不确定的物体具有矩形的不确定性区域。由于精确计算Voronoi细胞是一个困难的问题，我们提出了一个近似的解决方案。这种解决方案的主要思想是对数据空间和对象空间应用分层访问方法。我们的空间索引用于有效地找到必须（不）在Voronoi单元内的空间区域。我们的对象索引用于有效地识别Delauny关系，即，影响Voronoi单元形状的数据对象。我们提出并评估了一些算法下降的索引结构，并表明，这种方法下降的索引结构并行产生快速的查询处理时间。我们的实验表明，我们能够近似不确定的Voronoi细胞更有效地比国家的最先进的，并在同一时间，提高运行时的性能。
Voronoi diagrams are commonly used to answer traditional nearestneighbor queries in spatial databases. In this work, we propose a new approach to compute Voronoi-cells for the case of uncertain objects having rectangular uncertainty regions. Since exact computation of Voronoi-cells is a hard problem, we instead propose an approximate solution. The main idea of this solution is to apply hierarchical access methods for both data-space and object-space. Our space index is used to efficiently find spatial regions which must (not) be inside a Voronoi-cell. Our object index is used to efficiently identify Delauny-relations, i.e., data objects which affect the shape a Voronoi-cell. We propose and evaluate a number of algorithms to descend both index structures and show that the approach which descends both index structures in parallel yields fast query processing times. Our experiments show that we are able to approximate uncertain Voronoi-cells much more effectively than the state-of-the-art, and at the same time, improve run-time performance.