UM  > 科技學院  > 電腦及資訊科學系
G-Tree: An Efficient and Scalable Index for Spatial Search on Road Networks
Zhong R.3; Li G.3; Tan K.-L.2; Zhou L.3; Gong Z.1
2015-08-01
Source PublicationIEEE Transactions on Knowledge and Data Engineering
ISSN10414347
Volume27Issue:8Pages:2175-2189
Abstract

In the recent decades, we have witnessed the rapidly growing popularity of location-based systems. Three types of location-based queries on road networks, single-pair shortest path query, k nearest neighbor (kNN) query, and keyword-based kNN query, are widely used in location-based systems. Inspired by R -tree, we propose a height-balanced and scalable index, namely G-tree, to efficiently support these queries. The space complexity of G-tree is Ω(VlogV) where V is the number of vertices in the road network. Unlike previous works that support these queries separately, G-tree supports all these queries within one framework. The basis for this framework is an assembly-based method to calculate the shortest-path distances between two vertices. Based on the assembly-based method, efficient search algorithms to answer kNN queries and keyword-based kNN queries are developed. Experiment results show G-tree's theoretical and practical superiority over existing methods.

KeywordIndex Keyword Search Knn Search Road Network Single-pair Shortest Path Spatial Databases
DOI10.1109/TKDE.2015.2399306
URLView the original
Indexed BySCI
Language英语
WOS Research AreaComputer Science ; Engineering
WOS SubjectComputer Science, Artificial Intelligence ; Computer Science, Information Systems ; Engineering, Electrical & Electronic
WOS IDWOS:000357692600013
Fulltext Access
Citation statistics
Cited Times [WOS]:37   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionDEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Affiliation1.Universidade de Macau
2.National University of Singapore
3.Tsinghua University
Recommended Citation
GB/T 7714
Zhong R.,Li G.,Tan K.-L.,et al. G-Tree: An Efficient and Scalable Index for Spatial Search on Road Networks[J]. IEEE Transactions on Knowledge and Data Engineering,2015,27(8):2175-2189.
APA Zhong R.,Li G.,Tan K.-L.,Zhou L.,&Gong Z..(2015).G-Tree: An Efficient and Scalable Index for Spatial Search on Road Networks.IEEE Transactions on Knowledge and Data Engineering,27(8),2175-2189.
MLA Zhong R.,et al."G-Tree: An Efficient and Scalable Index for Spatial Search on Road Networks".IEEE Transactions on Knowledge and Data Engineering 27.8(2015):2175-2189.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zhong R.]'s Articles
[Li G.]'s Articles
[Tan K.-L.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhong R.]'s Articles
[Li G.]'s Articles
[Tan K.-L.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhong R.]'s Articles
[Li G.]'s Articles
[Tan K.-L.]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

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