论文部分内容阅读
随着移动设备的普及,人们积累了大量的轨迹数据。基于轨迹的路径推荐算法成为热点的研究问题。频繁路径算法(MFP)是经典的路径推荐算法之一,它通过轨迹重构权值图,以每条边被选择的次数即频繁度作为路径权值,进行路径的推荐。MFP算法推荐的路径虽然符合当地人开车的习惯,但是它推荐的路径可能包含过多的路口和过少的高等级路段(如高速路,快速路),并且算法的时间复杂度较大,实用性不强。为了解决MFP算法存在的问题,本文做了以下研究:首先本文提出了分层道路的频繁路径查询算法(RLMFP)。该方法在MFP的基础上,根据城市已有的道路级别规划,引入了路网分层的思想,降低了算法的复杂度。算法根据每条道路自身的级别抽象出高等级道路网络(快速路和高速路构成的路网),通过高等级网络利用广度优先遍历算法进行路网区域的划分,使用树结构进行分层网络的存储。然后算法通过分层网络路径推荐思想和MFP路径算法进行路径的推荐。接着本文采用基于嵌套哈希结构的快速索引(FG)对RLMFP算法展开了优化,提出了RLMFPT算法。MFP算法是一个无方向的路径查询算法,在分层道路路径算法中,它无法在低等级网络选择合适的升级点(高级网络和低级网络的交汇点)进入高级路网,需要计算起始点到所有升级点的MFP路径,这是造成RLMFP算法不稳定的原因。FG通过轨迹构建任意两个区域内的升级点索引结构来使RLMFP算法具备选择合适升级点的能力。FG的外层哈希表中,它以两个路网区域ID的组合(假定为A区域内的点前往B区域)为key,内层哈希表为value。内层哈希表中,它以起始区域路网(这里为A)内升级点为key,所有轨迹中满足起点为区域A终点为区域B并且经过该升级点的条件的轨迹总数作为value。论文通过理论分析证明了以上两个算法的合理性。论文在实际的出租车轨迹数据和模拟的轨迹数据上,通过实验说明RLMFP和RLMFPT算法推荐的路径比MFP更加合理,同时具有更快的响应速度。但是随着地图的增大,RLMFP算法的稳定性不足,对于升级点的数量依赖性较大。而RLMFPT算法较好的克服了这些缺点。