【作者】 张静；

【导师】 陈子军； 张淑杰；

【作者基本信息】 燕山大学 ， 工程硕士（专业学位）， 2017， 硕士

【摘要】 移动设备的不断增加和定位服务(如GPS)的快速发展,使得大量的数据轨迹被快速的生成和收集。传统的基于位置的轨迹搜索,给定一组查询点,从轨迹数据集中检索在地理空间上尽可能近的通过所有查询点的Top-k条轨迹。这种方式受到轨迹自身的限制,使得找到的轨迹并不能近距离通过所有点,或者轨迹到查询点所花费的时间过长,这使得找到的轨迹不能使用户满意。基于上述问题,本文扩展了传统的基于位置的轨迹搜索,考虑了时间因素和轨迹可拼接,提出了基于位置的个性化Top-k轨迹搜索。首先,针对轨迹可拼接的想法,提出基于位置的可拼接轨迹对搜索,这个方法可以返回可拼接的轨迹对,使用户利用轨迹对得到的轨迹比传统轨迹搜索得到的轨迹更加近距离地通过所有查询点。这个方法可以实现从一条轨迹到另一条轨迹的转换,减少了数据严重倾斜对搜索的影响。在搜索终止过程,定义搜索上、下界,并给出可拼接的轨迹对搜索过程的有效终止条件。其次,大部分的轨迹搜索都只关注位置信息,而忽略路况条件和旅行时间,这意味着只有空间上的距离最短被认为是最优轨迹。本文提出的基于位置的时空域个性化轨迹搜索,一方面关注每个查询点对于用户的意义,另一方面重新定义轨迹到查询点的距离函数,考虑在空间和时间上双标准的最优轨迹,使用户到达查询点的空间距离和时间距离都满意,更好地满足客户需求。在候选集验证时,利用上、下界进行裁剪,有效地提前终止,加快搜索速度。最后,在真实的数据集上对本文提出的两个算法与传统的轨迹搜索进行实验对比,验证本文所提出方法的有效性。更多还原

【Abstract】 The proliferation of mobile devices and the development of location-based services(e.g.,GPS),which generate and collect a large number of trajectories.Conventional location-based trajectory search in which context the query is only a small set of locations with or without an order specified,while the target is to find the Top-k trajectories from a database such that trajectories can be as close as possible to all locations geographically.However,retrieved trajectories of this way can’t go through all locations as close as possible,because it’s limited by trajectory itself.In addition,retrieved trajectories cannot satisfy users,because the travel time is too long from trajectory to all locations.Based on the above issues,this paper extends the conventional location-based trajectory search,considering two factors of travel time and splicing trajectories,we propose the personalized location-based trajectory search.First of all,location-based splicing trajectories pair search is proposed based on the idea that trajectory can spliced.This method can return trajectory pairs,and with the help of trajectory pairs,users can get trajectory which is closer to all the query points than that returned by conventional location-based trajectory search.With this method,transformation from one trajectory to another trajectory can be achieved,and the influence of trajectories with non uniform distribution on search is reduced.For the termination of search process,the upper bound and the lower bound are defined and an effective termination condition of the search process of splicing trajectory pairs search is given.Next,most of the trajectory search only focus on spatial information,but ignore traffic conditions and travel time.This means only the shortest distance on geography is considered to be the optimal trajectory.This paper proposes spatial-temporal domain personalized trajectory search by location.On the one hand,it pays attention to the significance of every query point to the user and assigns a weight to every query point,on the other hand,we redefine the distance function of trajectory to query: It also considers the travel time in temporal domain and the distance in spatial domain,which makes users satisfied with travel time and distance.For candidate validation,upper bound and lower bound are used to prune trajectories,to terminate search efficiently.At last,on the real data set,two algorithms proposed in this paper are compared with traditional trajectory search,which verifies the efficiency of the two algorithms in this paper.更多还原