K-Nearset Neighbor L-Close Friends Search On Road-Social Networks

With the rapid development of data analysis and processing technology,location-based services are increasingly being applied to people's real lives.The popularization of mobile smart devices has produced a large amount of spatial network data,which provides a basis for researching various queries of spatial databases.Nearest neighbor query has been a key research object in academic and commercial fields since it was put forward.This article studies the Road-Social Networks k-Nearest l-Close Friend Query(RSkl-NCF).First,a Dijkstra-based RSkl-NCF query algorithm(D-RSNCF)is proposed.This method first uses a hash table to store user vertices in the required l-hop friends list of the query user and the information on the edges of the road network where all friends are located,and then uses the Dijkstra algorithm to expand the query on the road network,judges the user objects on the side of the expansion,and finds the top-k neighbor user objects that conform to the social relationship.It also proposes an early termination strategy,that is,when the eligible edges are all traversed,or the number of results returned is greater than or equal to k,and the maximum distance in the result set is equal to the minimum distance in the closed but not visited set,it can be terminated early to avoid continuing traverse the road network in order to reduce unnecessary calculations.Secondly,the RSkl-NCF query algorithm(L-RSNCF)based on IS-Label is designed.Build the R-Tree index for all the edges of the user objects that meet the intimacy.Then we use the Best-First algorithm to query,using the IS-Label index to calculate the shortest distance between two points.It also proposes an early termination strategy,that is,when the number of returned results is greater than or equal to k,and the maximum road network distance in the result set is equal to the minimum Euclidean distance stored in the priority queue,it can be terminated early to avoid unnecessary calculations.This method is very suitable for querying users who are far away from their friends.Finally,different datasets are used to verify the effectiveness of the proposed algorithm.