Shortest Distance Query And Spatial Keyword Query Based On Key Nodes On Road Networks

With the rapid development of the Internet economy and the popularization of mobile terminals,location-based services(LBS)is developing rapidly.At the same time,with the development and improvement of the road networks,there are huge number of spatial textual objects accumulated on the road networks.The shortest distance query between two vertices on the networks has become a hotspot in the database field.In order to achieve related queries in the road networks,people have proposed some innovative indexing technologies,such as G-tree and G*-tree,which divide the road networks space by region and then organize it in a tree structure.Although the existing technologies can effectively divide and organize the road networks,there is still the room for further improvement in query efficiency.For example,the hub-labeling method requires many time and memory resources to process the shortest distance query problem on the large-scale road networks.According to the investigation,it is obvious that the existing shortest distance query processing methods cannot effectively satisfy users' query operations on large-scale road networks.Therefore,this paper studies the shortest distance query problem in large-scale road networks space and designs a novel index structure LG-tree and corresponding query algorithm.The main contribution of this paper is as follows:First,in order to achieve the shortest distance query on the large-scale road networks,based on the inspiration of graph segmentation and labeling technology,employing G-tree as the basic structure,this paper proposes an efficient LG-tree index structure;The construction idea of LG-tree is as follows:Employ graph segmentation technology to partition segment the large graph,find all the boundary vertices,marks the levels for these boundary points,and add label information.Making use of the label information of the boundary points,the shortest distance between the sub-images can be quickly determined.In order to improve the query efficiency,we propose an N-level method.which employ a heuristic method to restrict the level of the border vertices.In order to reduce the amount of computation during distance query,each leaf node of LG-tree is equipped with a DIF inverted file.DIF stores the shortest distance information betwveen the boundary points of all child nodes of the current node.Second,based on the proposed LG-tree index structure,this paper proposes a shortest distance query algorithm based on dynamic programming.According to the location relationship between the query point and the target point,the algorithm selects the different query strategies reasonably.This article expands the label information of LG-tree to realize the shortest distance path query.We have conducted comparative experiments on real-world data set,which shows that our methods is efficient.Third,considering there are huge number of spatial textual objects accumulated on the road networks,the spatial textual objects are becoming more importation when LBS provides some services.Based on the LG-tree structure,this paper studies the problem of spatial keywords in the road networks and designs a new one Similarity function and spatial text index TLG-tree.Based on TLG-tree,the paper propose the CM algorithm to query the top k spatial text objects in the road networks.Experimental results show that the CM algorithm is effective.