The Research On Technologies Of Predicting Next Location Based On Historical Trajectory

Predicting users’ future location can be divided into two sub-problems, i.e.obtaining significant places from history trajectories and predicting locations based onstatistical models. This paper presents new approaches to deal with both of the aboveproblem. In fact, people always travel around the traffic road network. Taking this factinto consideration, this paper also studies the problem of location prediction in theroad network environment and proposes an efficient method. The main work is asfollows:Firstly, this paper proposes a method which is based on the definition ofcoherence to find stay points. The key problem of finding significant places is how toextract stay points from history trajectories. Stay points are the locations where peoplespeed a period of time to do something important. However, the existing approachesto this problem are too simple, loses many possible ones, and they perform poorlywhen the trajectories are low-sampling-rate. Taking the above shortcomings intoaccount, this paper uses coherence to estimate the features of stay points, which arethe higher density and lower speed. Then we present the stay points extractingalgorithm based on coherence which is similar to DBSCAN cluster algorithm workedby selecting seed trajectory points to extend out under coherence.Secondly, this paper comes up with a predicted method which needs loweramount of space and can deal with zero frequency problem. There are drawbacks likehigh space complexity and zero frequency problem in traditional predicted modelbased on matrix. So we train a variable order Markov Model to predict next location.The variable order Markov Model uses escape mechanism to address the zerofrequency problem and uses a tree structure to decrease the amount of memory neededin traditional predicted model.Thirdly, this paper presents a predicted approach based on Voronoi diagramwhich can work out the predicted troubles under road network and super largeamounts of trajectory data. Road network is complex and has a large amount ofcrossroads and roads. The method which is based on the hierarchical clusteringalgorithm min semantic trajectories effectively. However, this method need a largeamount of time and ignore the fact that people travel based on the road network. Thispaper presents an approach based on Voronoi diagram to address the predicted issues in the road network environment using large scale trajectory data. Firstly, theproposed method uses Voronoi diagram to divide the map, then translates the historytrajectories to semantic trajectories which are indicated by Voronoi cells according thevisited time. After that, we learn predicted model and predict users’ next locationbased on the learned model.In summary, on the basis of analysis of existing researches, this paper studies themethod to extract stay points, predicted model and predicted algorithm about largeamount of trajectory data. The experiment results have shown that the proposed staypoints extraction method achieve better effect, location prediction approach based onthe VOMM needs fewer space and have better accuracy, and the method based onVoronoi diagram can handle predicted problems under road network environment.This study helps to facilitate the technologies of real-time online LBS service.