Author(s): L.Sundarrajan, K.Gopinath, V.Praveen, Dr. P.Gomathi, A.Jenifer

In the recent decades, Those have witnessed the rapidly growing popularity of locationbased 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.