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.

Google ScholarTM



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