Instance optimal query processing in spatial networks

Deng, Ke, Zhou, Xiaofeng, Shen, Heng Tao, Sadiq, Shazia and Li, Xue (2009) Instance optimal query processing in spatial networks. The VLDB Journal, 18 3: 675-693. doi:10.1007/s00778-008-0115-0

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

Author Deng, Ke
Zhou, Xiaofeng
Shen, Heng Tao
Sadiq, Shazia
Li, Xue
Title Instance optimal query processing in spatial networks
Journal name The VLDB Journal   Check publisher's open access policy
ISSN 1066-8888
Publication date 2009-06-01
Year available 2009
Sub-type Article (original research)
DOI 10.1007/s00778-008-0115-0
Open Access Status
Volume 18
Issue 3
Start page 675
End page 693
Total pages 19
Place of publication Heidelberg, Germany
Publisher Springer
Language eng
Abstract The performance optimization of query processing in spatial networks focuses on minimizing network data accesses and the cost of network distance calculations. This paper proposes algorithms for network k-NN queries, range queries, closest-pair queries and multi-source skyline queries based on a novel processing framework, namely, incremental lower bound constraint. By giving high processing priority to the query associated data points and utilizing the incremental nature of the lower bound, the performance of our algorithms is better optimized in contrast to the corresponding algorithms based on known framework incremental Euclidean restriction and incremental network expansion. More importantly, the proposed algorithms are proven to be instance optimal among classes of algorithms. Through experiments on real road network datasets, the superiority of the proposed algorithms is demonstrated. © Springer
Keyword Spatial networks
Spatial queries
Instance optimality
Incremental lower bound constraint
Q-Index Code C1
Q-Index Status Provisional Code
Grant ID DP0663272
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collection: School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 16 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 30 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Thu, 03 Sep 2009, 18:03:46 EST by Mr Andrew Martlew on behalf of School of Information Technol and Elec Engineering