Reverse K Nearest Neighbor Query On Semantic Trajectories

With increasing popularity of mobile devices and flourish of social networks,semanticenriched trajectories retrieval has received great attentions in recent years.Various queries have been proposed for matching users' spatial and textual requirements on these trajectories.Reverse k Nearest Neighbors query Semantic Trajectories(Rk NNST)is to find out the track set which is one of the k nearest neighbor candidate sets related to the query text as the spatial text information of the track itself.The main research contents are as follows:First,the k-nearest neighbor query is reversed according to the semantic trajectory,that is,the semantic key matching constraint is required,and the range constraint of the trajectory and the spatial position of the query point is required.A new index structure index tree is proposed,which uses the inverted table to store the keyword information of the semantic track,uses the M tree to store the global fuzzy position of the track in the tree node,and uses the node to connect the B+ tree to store the accurate position information.It is convenient to make distance judgments on the whole and local levels.Secondly,for the semantic trajectory reverse k,the correlation distance between the trajectory and the query point in the nearest neighbor query needs to enumerate all the subtrack combinations containing the text keyword information to calculate the correlation distance.The related distance algorithm is designed.The inverted key table is used to store the track keywords,and the query point keywords are used for pointer matching,and the corresponding points are selected to form sub-tracks.Based on the correlation distance algorithm,a brief query algorithm for the reverse k nearest neighbor query is proposed.This algorithm is mainly based on the track index tree access,and uses the track index tree node to alternately access the query index tree to determine whether the track in the track index tree node is the reverse k nearest neighbor track.Finally,for the query algorithm to access the track index tree node alternately,the actual efficiency is relatively low.According to the track index tree node,the geometric distance characteristics between the index tree and the query point are proposed to propose the pruning rules,and the rules are theoretically proved.When the track index tree node accesses the query index tree node,rules can be used to determine whether to access the node and the child nodes of the node,reduce unnecessary node access,and reduce the running time of the algorithm.Then use the real user data set to conduct multiple sets of experiments,and compare it with the NA,W,and WI algorithms that do not contain indexes under various conditions.