【作者】 张得天；

【导师】 张信明； 许胤龙；

【作者基本信息】 中国科学技术大学 ， 计算机软件与理论， 2014， 博士

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

【Abstract】 Spatio-temporal queries have been widely used in location-based services (LBS). Despite the importance of travel time in road networks, the distance measure of tra-ditional spatio-temporal queries for LBS, e.g., k-nearest-neighbor (k-NN), is mostly based on Euclidean or network distance between two locations, which can not reflect the real travel time. In this thesis, we focus on k-NN queries, in time-dependent road networks, where the travel time between two locations may vary significantly at dif-ferent time of the day. In practice, it is costly for an LBS provider to collect real-time traffic data from vehicles or roadside sensors to compute the best route from a user to a spatial object of interest in terms of the travel time. Thus, a server-side spatial mashup framework is designed that enables an LBS provider to efficiently evaluate spatio-temporal queries using the route information and travel time accessed from an external Web mapping service, e.g., Microsoft Bing Maps, Google Maps, MapQuest Maps, Yahoo! Maps, Baidu Maps and so on. Due to the expensive cost and limita-tions of retrieving such external information, we propose pruning, grouping, direction sharing and parallel requesting optimizations to reduce the number of external Web mapping requests and user query response time, and integrate them into k-NN queries using spatial mashups. In summary, the main contribution of this thesis as follows:· A new framework is proposed, which uses a server-side spatial mashup paradigm for an LBS provider, by accessing travel time and direction information from Web mapping services, to process spatio-temporal queries in a time-dependent road network.· We have utilized pruning techniques to reduce the number of external requests by pruning objects that are definitely not be part of query answers, and designed an algorithm to processing k-NN queries by combining pruning techniques with network expansion algorithm.· Grouping optimizations are designed by grouping objects and users to intersec- tions based on the road network topology and user moving directions to achieve shared execution, which is a first attempt to do this kind of grouping as far as we know. This kind of grouping optimization can heavily reduce the number of external request while keeps the high accuracy of travel time and query answers.· To further reduce the number of external requests, another shared execution op-timization called direction sharing is proposed, which try to make the route be-tween a source to a destination be shared used by other sources and their corre-sponding destinations. A histogram approach is also employed to estimate the sharing ability for a route to make full utilization of the direction sharing opti-mization.· We have presented a totally new parallel requesting approach to reduce response time for a single user query, exploited inter-query cooperation and incremental processing for a system with high workload (e.g., a large number of user queries arrived concurrently or in succession), brought forth and solved the starvation problem during incremental processing.更多还原