Research And Realization Of Reverse K Nearest Neighbor Query Processing Technology In Time-dependent Network

Reverse k nearest neighbor query is an important query related to position in spatial database,Which points of interest it retrieves to query for point q as one of its kNN query results.Since it was proposed,it has always been the focus of researchers at home and abroad,However,the existing efficient reverse k nearest neighbor query methods are mostly implemented in the European-style space or the static road network environment,and there are relatively few studies on the reverse k nearest neighbor query in the time-dependent road network.In the reverse k nearest neighbor query algorithm in the time-dependent network,the existing mTD-Eager algorithm performs a range query on each node in the search path,which requires a longer processing time.The mTD-Eager algorithm finishes faster when the points of interest density is larger and the k value is smaller.However,when the density of points of interest is low or the value of k is large,the query time becomes longer and the number of traversal nodes increases due to the larger search range,resulting in lower query efficiency.In this regard,this paper presents a grid-based reverse k nearest neighbor query algorithm mTD-SubG.First,the entire road network is divided into grids of the same size,and the grid nodes are expanded to other grids through boundary nodes to speed up the search for points of interest in the road network.Then,the pruning technology is used to reduce the expansion range of the road network.Finally,we use the already-existing time-dependent neighbor query algorithm to find out whether the interest point is the reverse k nearest neighbor result.However,when meshing the road network,if the grid is too large or too small,it will affect the efficiency of reverse k nearest neighbor query.Therefore,this paper improves the mTD-SubG algorithm and proposes the mTD-SubG-Imp algorithm,which combines adjacent grids that do not contain points of interest and reduces the number of nodes that do not contain points of interest Expansion,thereby reducing the query response time and the number of nodes traversal and improve the query efficiency.In this paper,we compare and verify the performance of the mTD-SubG algorithm and the mTD-SubG-Imp algorithm based on meshing and the existing algorithms proposed in this paper with the real map data and simulation data set.In terms of query response time,mTD-SubG-Imp algorithm has the fastest query response,which is 73% shorter than the existing one.The mTD-SubG-Imp algorithm has the highest query efficiency in traversing the number of nodes,which is 48.4% less than the existing one.Verify the correctness and efficiency of the proposed algorithm.