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.
|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. https://doi.org/10.1145/2505515.2505749||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||URI:||http://scholarbank.nus.edu.sg/handle/10635/78164||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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.