A multi-resolution surface distance model for k-NN query processing 摘要粗译

多分辨率表面距离模式下的k-NN查询处理

Abstract Aspatial k-NN query returns k nearest points in a point dataset to a given query point. To measure the distance between two points, most of the literature focuses on the Euclidean distance or the network distance. For many applications, such as wildlifemovement, it is necessary to consider the surface distance, which is computed from the shortest path along a terrain surface. In this paper, we investigate the problem of efficient surface k-NN(sk-NN) query processing. This is an important yet highly challenging problem because the underlying environment data can be very large and the computational cost of finding the shortest path on a surface
can be very high. To minimize the amount of surface data to be used and the cost of surface distance computation, a multiresolution surface distance model is proposed in this paper to take advantage of monotonic distance changes when the distances are computed at different resolution levels. Based on this innovative model, sk-NN queries can be processed efficiently by accessing and processing surface data at a justenough resolution level within a just-enough search region. Our extensive performance evaluations using realworld datasets confirm the efficiency of our proposed model.

摘要:空间k-NN查询可以从一个点集中给定一个查询点中返回k个最近点.为了衡量两个点之间的距离,很多文献聚焦于欧几里德距离或网络距离.对于很多应用,比如野外生物移动,有必要去考虑其表面距离,沿着地域表面计算最短路径.本文中,我们研究了有效的表面k-NN查询处理技术.这是一个重要而且具有挑战性的问题,因为环境数据可能是非常大而且在表面寻找最短路径的计算的代价也是非常昂贵的.为了最少化使用的表面数据和缩小表面距离计算的代价,一个多分辨率的表面距离模式在本文中被提出来,文中充份利用了在不同的分辨率下的计算距离变化的单调性.在这种创新的模式下,通过读取和处理表面数据在特定的查找区域和分辨率下sk-NN查询可以被有效地处理.我们使用真实的数据集来广泛地评估确定我们的设计模式的效率.