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

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.