时间依赖路网高效k最近邻查询混搭机制的研究.doc

时间依赖路网高效k最近邻查询混搭机制的研究时空查询(如κ最近邻查询)被广泛地使用在基于位置服务(LBS)中,例如查找离我最近的五家饭店。尽管在路网中两点间的行驶时间非常重要,但已有时空查询的距离度量大部分都是基于物理距离,即欧几里得距离或网络距离,而这种距离度量并不能反映出行驶时间。但相对于物理距离,行驶时间具有高度动态性。路网中两点之间的行驶时间很难被实时而又准确预测。获取行驶时间最佳的方式是实时监控道路的交通状况,如部署摄像头、传感器以及收集车辆GPS信息等。然而,并不是每一个LBS提供者都有能力完成这种高代价的部署。因此本文中,我们为LBS提供者设计出了一个服务器端的地图混搭机制。采用这种地图混搭机制,LBS提供者利用从互联网地图服务商(如谷歌地图、必应地图、雅虎地图和百度地图等)获取的行驶时间和路径信息并结合本地数据来有效地处理来自用户的各种基于行驶时间的时空查询请求。互联网地图服务商拥有足够的财力和实力,通过多渠道收集数据(如实时交通状况和历史交通数据等)以计算或估算路网中给定两点间的行驶时间和路径信息。但是由于从互联网地图服务商获取数据的高代价性以及局限性,本文提出了修剪、分组、方向共享和并行请求等优化算法并结合κ最近邻查询特点,来减少LBS提供者向互联网地图服务商发送数据请求的次数和响应用户的时间。本文的主要研究内容及贡献总结如下：·为LBS提供者设计了一个服务器端的地图混搭机制。利用该机制,LBS提供者通过从互联网地图服务商获取行驶时间和路径信息,并结合本地数据,有效地处理路网中基于行驶时间的各项时空查询请求。·利用修剪技术,即在算法执行过程中不断修剪不必要的查询对象,来减少LBS提供者向互联网地图服务商发送数据请求的次数,并结合网络扩展算法来处理k最近邻查询请求。·设计出了分组优化策略,即把查询对象和用户分组到路网中交叉路口以实现共享执行,然后估算查询对象到其对应路口的行驶时间和路径信息。在保证查询结果高准确性的基础上,该分组算法能大大减少LBS提供者发送外部数据请求的次数。·提出了方向共享策略以进一步减少外部数据请求次数。该策略试图让一条包含详细行驶时间和方向信息的路径能被多个起点和其对应的终点共享使用。为了最大化利用方向共享执行,本文中还设计了一个直方图方法用以估算一条路径的共享能力。·研究了为相互独立路径并行发送数据请求到互联网地图服务商的策略,以降低LBS提供者响应查询用户的时间。此外,还充分挖掘了多用户查询间合作和增量执行以应对大规模用户查询请求,同时解决了增量执行中可能出现的饥饿问题。·对于本文设计的每一个算法,我们都通过了大规模的实验或模拟仿真验证了其准确性、高效性以及可扩展性。