GAM:A GPU-Accelerated Algorithm for MaxRS Queries in Road Networks
作者机构：School of Computer Science and TechnologyHarbin Institute of TechnologyHarbin150001China
出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)
年 卷 期：2022年第37卷第5期
页 面：1005-1025页
核心收录：
学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）]
基 金：This work was supported in part by the Key Research and Development Plan of National Ministry of Science and Technology under Grant No.2019YFB2101902 the National Natural Science Foundation of China under Grant Nos.U19A2059 and 62102119 the CCF-Baidu Open Fund CCF-BAIDUunder Grant No.OF2021011
主 题：road network maximizing range sum GPU acceleration pruning strategy
摘 要：In smart phones,vehicles and wearable devices,GPS sensors are ubiquitous and collect a lot of valuable spatial data from the real *** a set of weighted points and a rectangle r in the space,a maximizing range sum(MaxRS)query is to find the position of r,so as to maximize the total weight of the points covered by r(i.e.,the range sum).It has a wide spectrum of applications in spatial crowdsourcing,facility location and traffic *** of the existing research focuses on the Euclidean space;however,in real life,the user’s moving route is constrained by the road network,and the existing MaxRS query algorithms in the road network are *** this paper,we propose a novel GPU-accelerated algorithm,namely,GAM,to tackle MaxRS queries in road networks in two phases *** phase 1,we partition the entire road network into many small cells by a grid and theoretically prove the correctness of parallel query results by grid shifting,and then we propose an effective multi-grained pruning technique,by which the majority of cells can be pruned without further *** phase 2,we design a GPU-friendly storage structure,cell-based road network(CRN),and a two-level parallel framework to compute the final result in the remaining ***,we conduct extensive experiments on two real-world road networks,and the experimental results demonstrate that GAM is on average one order faster than state-of-the-art competitors,and the maximum speedup can achieve about 55 times.
维普期刊数据库