大规模最短路径查询关键技术研究

With the rapid development of mobile Internet and location-based services, shortest path queries have been becoming more and more available and popular. Focusing on the shortest path queries in large scale and high concurrency, the project attempts to investigate and accomplish two key technologies, i.e., path caching and path parallel computing, which can effectively reduce the computational complexity and the response time. The research of this project involves cache structure design, cache lookup algorithm, path prediction algorithm, cache updating algorithm, parallel computing architecture design, query distribution algorithm and path-query matching algorithm. It is an interdisciplinary research of spatial-temporal databases, cache technology and parallel computing, whose output will be significantly practical and valuable, as it can efficiently process the large-scale and high-concurrency shortest path queries in the actual navigation and location-based services.

随着移动互联网和位置服务的蓬勃发展，路径导航日趋流行，其查询规模也逐渐庞大。本项目针对这种大规模、高并发的最短路径查询，研究路径缓存和路径并行计算两种关键技术，并实现相应的原型系统，以减少服务器计算量和降低响应用户时间。本项目研究具体涉及缓存结构设计、缓存查找算法、路径预测算法和缓存更新算法等缓存技术，以及大规模路径并行计算架构设计、查询请求分发算法和路径请求匹配算法等并行计算技术。本项目研究内容为时空数据库、缓存技术和并行与分布式计算等三个领域最新的一个交叉融合课题。其研究成果能高效处理，导航与位置服务中实际存在的大规模、高并发最短路径查询，具有重大的实用价值和广阔的应用前景。

本项目针对导航和与位置服务领域实际存在的大规模、高并发最短路径查询问题，研究了高效的路径缓存算法及系统，并将相关理论移植到空间众包领域和大规模交通数据获取领域，均取得较好效果。在路径缓存方面，我们针对路网数据未知时研究了基于边的最短路径缓存，使缓存命中率能够提高2~4倍，响应时间降低60%~80%；针对动态路网研究了基于行驶时间的路径缓存以及路径连接算法，在可接受的路径误差范围内能有效提高缓存命中率和降低响应时间。在空间众包领域，针对路网数据未知时设计了基于网络地图服务的空间众包系统，以及剪枝和路径共享等优化算法以减少调用网络地图服务次数。在大规模交通数据获取领域，针对异构车载终端设计出了一个有效并且非阻塞的交通数据获取系统，以基于不同优先级和QoS需求提取不同类型交通数据。总而言之，在本项目的资助下，项目组在大规模高并发的路径查询、空间众包以及交通数据获取等领域均取得较好的研究成果。