Research And Implementation Of Spatial Indexing Method For Time Dependent Road Network

With the rapid development of wireless communication technology,global positioning system and geographic information system,the location of the service in the traffic guidance,vehicle tracking,child care,location query,emergency call in the field show broad application prospects based on the people for the location query services based on demand more,with the accelerated pace of life,high variable the time efficiency requirements,time dependent location query service under the network has more practical significance.The existing methods improve the location query quality of time dependent road network from the perspective of optimization algorithm.At present,we know that there is no time dependent index method to satisfy multiple types of interest Points query under the road network.This paper presents a spatial index structure with grid Points of interest distribution based on multi Points of interest distribution of time dependent network(TDG);first in the network conditions to ensure the integrity and connectivity,the use of mesh network space,according to the distribution of Points of interest types in the network from bottom to up the index structure.Put forward the path weights of lower bound pruning path pre computation based on the index construction optimization strategy,to reduce the storage space of pre computed paths.And the update strategy of index maintenance is put forward.Based on TDG index structure,three kinds of Spatio-temporal query algorithms,k nearest neighbor query,range query and fastest path query algorithm,are optimized,and the fastest path query algorithm is optimized.Using real map data simulation results shown that when the distribution of multiple types of interest points is sparse,the number of average extended nodes of the k nearest neighbor query algorithm based on TDG is 87.5% less than that of heuristic query algorithm.And the average query response time is 33% to 66% less than that of heuristic query algorithm;the number of average extended nodes of the range query algorithm based on TDG is 33% less than that of heuristic query algorithm.And the average query response time is 50% less than that of heuristic query algorithm;the number of average extended nodes and the average query response time of the fastest path query algorithm based on TDG are 34% to 60% less than that of heuristic query algorithm.It can be seen that the Spatio-temporal query algorithms based on TDG has obvious advantages when the distribution of interest points is sparse and can efficiently support multi type of interest point query.