Reverse Top-k Keywords-based Location Query On Road Network

With the prosperity and development of data processing technology,location-based services are increasingly used in people's lives.The popularity of mobile devices has produced a large number of spatial network objects with textual information.These data provide the basis for studying spatial database query problems.Reverse nearest neighbor query is a key research object in the academic and commercial fields in recent years.This article makes an in-depth exploration of the Reverse Top-k keyword-based location query on road network(RrTkKL).First,the RrTkKL query based on valid vertices is proposed.This method proposes the concept of valid vertices.Starting from the query point,the Dijkstra algorithm is used to expand the road network until all valid vertices are found.If every vertex on the road network is judged,the invalid workload will be very large,so an early termination strategy is proposed to avoid verifying the vertex of the entire road network.When judging whether v is a valid vertex,a corresponding cropping strategy is proposed to keep only objects within a certain range and reduce the calculation of invalid objects.Then it traverses the adjacent edges of all valid vertices and uses the idea of continuous search to find valid line segments.Then,in order to further improve the performance of the query algorithm,RrTkKL query based on the network Voronoi diagram is proposed.Inspired by the Voronoi diagram of the network,the concept of bisector is proposed.As the road network is complex and diverse,the concept of diamond model is proposed.Using the diamond model as the frame,calculate the boundary points for each edge separately.Since not all objects and the query point can produce a boundary point on this edge of the current traversal,a corresponding cropping strategy is proposed.Boundary points are provided with directional attributes.When counting the number,specify "increase by 1 in the same direction and decrease by 1 in the opposite direction",so as to ensure the accuracy of the counting of the boundary points.Every time a vertex v out of the queue can determine its boundary point count,using the count of v and k for comparison can terminate the extended road network in advance.Finally,the experimental comparison analysis is carried out with different data sets to verify the efficiency of the proposed algorithm.