Please use this identifier to cite or link to this item:
Title: G-tree: An efficient index for KNN search on road networks
Authors: Zhong, R.
Li, G.
Tan, K.-L. 
Zhou, L.
Keywords: KNN search
Road network
Spatial databases
Issue Date: 2013
Citation: Zhong, R.,Li, G.,Tan, K.-L.,Zhou, L. (2013). G-tree: An efficient index for KNN search on road networks. International Conference on Information and Knowledge Management, Proceedings : 39-48. ScholarBank@NUS Repository.
Abstract: In this paper we study the problem of kNN search on road networks. Given a query location and a set of candidate objects in a road network, the kNN search finds the k nearest objects to the query location. To address this problem, we propose a balanced search tree index, called G-tree. The G-tree of a road network is constructed by recursively partitioning the road network into sub-networks and each G-tree node corresponds to a sub-network. Inspired by classical kNN search on metric space, we introduce a best-first search algorithm on road networks, and propose an elaborately-designed assembly-based method to efficiently compute the minimum distance from a G-tree node to the query location. G-tree only takes O(|V | log |V |) space, where |V | is the number of vertices in a network, and thus can easily scale up to large road networks with more than 20 millions vertices. Experimental results on eight real-world datasets show that our method significantly outperforms state-of-the-art methods, even by 2-3 orders of magnitude. Copyright 2013 ACM.
Source Title: International Conference on Information and Knowledge Management, Proceedings
ISBN: 9781450322638
DOI: 10.1145/2505515.2505749
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Dec 10, 2018

Page view(s)

checked on Dec 8, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.