Surface k-NN query processing

Deng, Ke, Zhou, Xiaofang, Shen, Heng Tao, Xu, Kai and Lin, Xuemin (2006). Surface k-NN query processing. In: Ling Liu, Andreas Reuter, Kyu-Young Whang and Jianjun Zhang, Proceedings of the 22nd IEEE International Conference on Data Engineering (ICDE 2006). 22nd International Conference on Data Engineering (ICDE 2006), Atlanta, GA, United States, (1-11). 3-8 April 2006. doi:10.1109/ICDE.2006.152

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
MIC12UQ104450.pdf Full text - not publicly available application/pdf 246.54KB 0

Author Deng, Ke
Zhou, Xiaofang
Shen, Heng Tao
Xu, Kai
Lin, Xuemin
Title of paper Surface k-NN query processing
Conference name 22nd International Conference on Data Engineering (ICDE 2006)
Conference location Atlanta, GA, United States
Conference dates 3-8 April 2006
Proceedings title Proceedings of the 22nd IEEE International Conference on Data Engineering (ICDE 2006)
Place of Publication Los Alamitos, CA United States
Publisher IEEE
Publication Year 2006
Sub-type Fully published paper
DOI 10.1109/ICDE.2006.152
ISBN Online proceedings
Editor Ling Liu
Andreas Reuter
Kyu-Young Whang
Jianjun Zhang
Start page 1
End page 11
Total pages 11
Collection year 2006
Language eng
Abstract/Summary 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.
Subjects E1
280103 Information Storage, Retrieval and Management
700103 Information processing services
Q-Index Code E1
Q-Index Status Provisional Code
Institutional Status UQ
Additional Notes Published as an abstract in print proceedings: ISBN: 0-7695-2570-9, p. 78

Version Filter Type
Citation counts: Scopus Citation Count Cited 4 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Thu, 23 Aug 2007, 22:23:19 EST