Surface k-NN Query Processing 摘要粗译

Abstract
A k-NN query finds the k nearest-neighbors of a given point from a point database. When it is sufficient to measure object distance using the Euclidian distance, the key to efficient k-NN query processing is to fetch and check the distances of a minimum number of points from the database.For many applications, such as vehicle movement along road networks or rover and animal movement along terrain surfaces, the distance is only meaningful when it is along a valid movement path. For this type of k-NN queries, the focus of efficient query processing is to minimize the cost of computing distances using the environment data (such as the road network data and the terrain data), which can be several orders of magnitude larger than that of the point data. Efficient processing of k-NN queries based on the Euclidian distance or the road network distance has been investigated extensively in the past. In this paper, we investigate the problem of surface k-NN query processing, where the distance is calculated from the shortest path along a terrain surface. This problem is very challenging, as the terrain data can be very large and the computational cost of finding shortest paths is very high. We propose an efficient solution based on multiresolution terrain models. Our approach eliminates the need of costly process of finding shortest paths by ranking objects using estimated lower and upper bounds of distance on multiresolution terrain models.

摘要
k-NN查询，是从一个点集当中查找第K个最近邻居点。当使用欧几里德距离，进行有效地测量对象距离时，有效的k-NN查询处理的关键是抓住并且检查数据库中的最小数量点的距离。对很多应用，如果沿着公路网络中的行进的车辆，或者在一个区域表面浮动的物品或移动的动物，只有它有效地沿着路径移动时，距离才有意义。对于这种类型 的k-NN查询，研究的焦点在于使用环境数据（比如交通网络或地型数据），来有效查询处理距离计算的最小代价。这种数据与点数据相比，可能会是成级数倍的大小。有效地处理k-NN查询基于欧几德欧离或公路网络距离在过去已经被广泛地研究过。本文中，我们研究表面k-NN查询处理问题，这种距离是基于沿着空间表面的最短路径。本问题是非常有挑战性的，因为地域数据非常大并且找查最短路径的代理非常高昂。我们设计了一个有效的基于多辨率地型模型的有效解决方案。我们在多辨率地型模型中，利用等级对象下界或上界距离来进行查找最短路径处理的代价估计。