基于请求聚簇的最短路径流处理方法  

Stream Processing Method of Shortest Path Based on Query Cluster

作　　者：余昊 熊汉江[1] YU Hao;XIONG Hanjiang(State Key Laboratory of Information Engineering in Surveying Mapping and Remote Sensing,Wuhan University,Wuhan 430079,China)

机构地区：[1]武汉大学测绘遥感信息工程国家重点实验室,湖北武汉430079

出　　处：《测绘与空间地理信息》2025年第2期103-106,共4页Geomatics & Spatial Information Technology

摘　　要：随着智能手机的快速发展以及移动位置服务的广泛应用,最短路径请求一刻不停地从世界各地发往位置服务端执行计算,最终造成的高并发请求流给人们带来了新的挑战。针对此问题,本文研究了流处理场景下的最短路径计算方法。首先,基于搜索空间估计完成请求聚簇;其次,在实际计算之前,增添缓存层,利用部分匹配方法充分发挥缓存的优势并设计相应的高效数据结构负责缓存查询;最后,在计算层,改进传统预处理算法,将预处理阶段隐含在路径计算过程中,并缩小了计算的平均搜索空间规模。实验结果表明,该方法可以应对高并发请求流,且相比传统方法,计算加速效果良好。With the rapid development of smartphones and the popularity of location-based services,shortest path requests are sentto the location server side for computation all the time,which eventually causes a high concurrent request flow and brings us new challenges.To address this problem,this paper studies the shortest path computation method in the stream processing scenario.Firstly,query cluster is completed based on search space estimation;secondly,before the actual computation,a caching layer is added to take full advantage of the cache by using partial matching methods and designing the corresponding high efficient data structures responsible for caching queries;finally,in the computation layer,the traditional preprocessing algorithm is improved by implicitly including the preprocessing stage in the path computation process and reducing the average search space size of the computation.The experimental results show that the method can cope with high concurrent request streams and has good computational acceleration compared to the traditional methods.

关 键 词：最短路径 流处理 请求聚簇 部分匹配 

分 类 号：P208[天文地球—地图制图学与地理信息工程]