基于用户活动的路径查询技术研究

发布时间：2021-02-12 01:39

　　活动轨迹查询是当前基于位置服务研究的热门课题。活动轨迹是指带有用户活动关键字的轨迹,这类轨迹的查询算法结合了传统轨迹查询和空间关键字查询两个方面的技术,不仅允许用户输入多个目标地点作为查询地点,而且允许用户输入想要安排的活动作为查询条件的一部分去搜索匹配的活动轨迹。但是目前的活动轨迹查询研究注重于关键字的匹配而忽视了地理空间距离的限制。由这些算法得到的活动轨迹虽然完全匹配了用户活动需求,但却因关键字匹配要求和现实原因使得轨迹只能接近部分查询点而远离另一部分用户查询点。然而用户需要的是在查询点附近的轨迹路线,但是算法提供的这些轨迹却偏离了用户对于地理位置的需求。本文针对上述活动轨迹查询算法中存在的缺点,深入研究了活动轨迹和用户查询的匹配问题,并提出了轨迹段的匹配方法。该方法将整条活动轨迹划分为一段段的活动轨迹片段,然后找出能够匹配部分用户查询活动的那些轨迹片段,并将这些轨迹片段连接起来组成一条能够完整匹配用户查询活动且接近用户查询点的轨迹提供给用户。基于上述匹配思想,本文提出两种活动轨迹片段的搜索算法,有序匹配的活动轨迹片段搜索算法（OATSS）和活动轨迹片段扩展算法（ATSE）,去解决... 

【文章来源】：杭州电子科技大学浙江省

【文章页数】：69 页

【学位级别】：硕士

【部分图文】：

路径查询示例

象成图论里的一张图，每一条道路构成了图中的边集，道路的交叉路口和终点起点等组成了图中的点集。图中每条边的权值就相当于道路的某项属性，比如长度、车流速度、通过时间等等。如图2.1所示，北京的主干道路和交叉路口组成了点集和边集，并由此构成一张路网图。当用户给定起始点和终点时，这类路径查询方法就可以调用图论中经典的最短路径搜索算法（Dijkstra算法），得到一条起始点到终点的目标路径。图2.1：北京路网示例但是现实中道路交通网络的点和边的数量庞大，Dijkstra算法难以在短时间内找到一条从起点到终点的最短路线，由此许多研究人员纷纷提出改进策略来提高搜索效率[11-13,18-19]。在论文[11]中，作者提出使用启发式搜索策略取代全局搜索，由此得到路径搜索的A*算法。在启发式搜索中，A*算法使用一个评估函数来评估经过这些中间节点的路径的权重

近对方的点对距离总和，由此得到一个最小值作为轨迹相似性的度量值。但是这些方法着眼于轨迹中轨迹点的匹配，并没有考虑干扰因素。当轨迹的采样频率不一致时，轨迹相似性的度量值误差就会变大。如图2.2所示，A路线采样频率比B路线采样频率低。这样两条轨迹虽然非常相似，但是因采样频率不同，由上述距离公式得到的度量值误差无可避免的偏大。因此在论文[43]中，作者将采样频率加入考虑，提出新的评估轨迹相似性方法来衡量轨迹相似性。作者通过线性插值的方法将两条轨迹的采样频率变得接近，由此就可以通过上述距离公式来计算得到轨迹相似性的度量值。图2.2 采样频率不同轨迹示例基于上述轨迹相似性的研究，在论文[37]中，作者提出一种k-BCT的轨迹搜索算法。该算法的目标是搜索出整体距离用户查询最近的轨迹，因此轨迹相似性公式就设计成轨迹中距离查询点最近的那个轨迹点到查询点的距离。如果查询点有多个

【参考文献】：
期刊论文
[1]人类活动轨迹的分类、模式和应用研究综述[J]. 李婷,裴韬,袁烨城,宋辞,王维一,杨格格.  地理科学进展. 2014(07)
[2]利用位置签到数据探索城市热点与商圈[J]. 胡庆武,王明,李清泉.  测绘学报. 2014(03)
[3]车辆定位与导航系统中的快速路径规划算法[J]. 彭飞,柳重堪,张其善.  北京航空航天大学学报. 2002(01)



本文编号：3030045