A multi-resolution surface distance model for k-NN query processing

Deng, Ke, Zhou, Xiaofang, Shen, Heng Tao, Liu, Qing, Xu, Kai and Lin, Xuemin (2008) A multi-resolution surface distance model for k-NN query processing. The VLDB Journal, 17 5: 1101-1119. doi:10.1007/s00778-007-0053-2

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

Author Deng, Ke
Zhou, Xiaofang
Shen, Heng Tao
Liu, Qing
Xu, Kai
Lin, Xuemin
Title A multi-resolution surface distance model for k-NN query processing
Journal name The VLDB Journal   Check publisher's open access policy
ISSN 1066-8888
Publication date 2008-08
Year available 2007
Sub-type Article (original research)
DOI 10.1007/s00778-007-0053-2
Volume 17
Issue 5
Start page 1101
End page 1119
Total pages 19
Place of publication Heidelberg, Germany
Publisher Springer
Language eng
Subject 0806 Information Systems
890205 Information Processing Services (incl. Data Entry and Capture)
080604 Database Management
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.
Keyword k-NN query
Surface data
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status UQ
Additional Notes Published online: 26 June 2007

Document type: Journal Article
Sub-type: Article (original research)
Collections: Excellence in Research Australia (ERA) - Collection
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 3 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 11 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Thu, 03 Sep 2009, 09:50:34 EST by Mr Andrew Martlew on behalf of Faculty Of Engineering, Architecture & Info Tech