A multi-resolution surface distance model for <Emphasis Type="Italic">k</Emphasis>-NN query processing |
| |
Authors: | Ke Deng Xiaofang Zhou Heng Tao Shen Qing Liu Kai Xu Xuemin Lin |
| |
Affiliation: | (1) School of Information Technology and Electrical Engineering, The University of Queensland, Brisbane, QLD 4072, Australia;(2) National ICT Australia, Australian Technology Park, Eveleigh, NSW 1430, Australia;(3) School of Computer Science and Engineering, University of New South Wales, NICTA, Sydney, NSW 2052, Australia |
| |
Abstract: | A spatial 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 wildlife movement, 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 multi-resolution 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 just-enough resolution level within
a just-enough search region. Our extensive performance evaluations using real world datasets confirm the efficiency of our
proposed model. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|