A G-TREE BASED EFFICIENT AND SCALABLE INDEX FOR SPATIAL SEARCH IN LOCATION BASED SERVICE

In the recent decades, Those 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, That propose a height-balanced and scalable index, namely G-tree, to efficiently support these queries. The space complexity of G-tree is O (|V|log|V|) where |V| is the number of vertices in the road network. Unlike previous works 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 short-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.