图最短路径并行化及其应用研究

Research on parallelization of shortest path for graph and its application

当前计算机步入移动计算时代,产生了许多新的应用,其中基于地理信息系统和位置服务的地图查询——导航就是其中之一。这类应用可以抽象为求图最短路径问题,由于节点数量巨大,传统方式不能满足用户对响应时间的要求,提出通过C/S架构来合理分配任务,并在Server端对图最短路径进行了多核、多机等不同层次的并行化,以满足用户对实时性的需求。通过对该方法和传统方法的对比评估,该方法有效缩短了用户的等待时间,提高了用户的满意度,同时减少了对移动设备电量的消耗。

The current computer has been brought into the age of mobile computing that generates a number of applications.As one of these applications,the navigation is considered to be the map inquiry based on the geographical information system and location-based service.This application can be converted into achieving the shortest path.Due to the large number of nodes,the traditional method can＇t satisfy the user with the response time.In order to meet the actual requirement,this paper assigns tasks reasonably via the C/S framework and parallelizes the shortest path in the server side using polykaryon,multimachine and so on.Comparing with the traditional methods,the proposed approach saves latency time,increases the degree of satisfaction,and decreases the electricity consumption for the mobile device.