In smart phones,vehicles and wearable devices,GPS sensors are ubiquitous and collect a lot of valuable spatial data from the real world.Given 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 monitoring.Most 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 inefficient.In this paper,we propose a novel GPU-accelerated algorithm,namely,GAM,to tackle MaxRS queries in road networks in two phases efficiently.In 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 checking.In 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 cells.Finally,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.

Jian Chen;Kai-Qi Zhang;Tian Ren;Zhen-Qing Wu;Hong Gao

School of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001,China

计算机科学技术学报（英文版）

[1]Jian Chen;Kai-Qi Zhang;Tian Ren;Zhen-Qing Wu;Hong Gao-.GAM:A GPU-Accelerated Algorithm for MaxRS Queries in Road Networks)[J].计算机科学技术学报（英文版）,2022(05):1005-1025

MaxRS,pruned

GAM,GPU,Accelerated,Algorithm,Queries,Road,Networks,In,smart,phones,vehicles,wearable,devices,GPS,sensors,are,ubiquitous,collect,lot,valuable,spatial,data,from,real,world,Given,set,weighted,points,rectangle,space,maximizing,range,sum,query,find,position,maximize,total,covered,by,It,wide,spectrum,applications,crowdsourcing,facility,location,traffic,monitoring,Most,existing,research,focuses,Euclidean,however,life,user,moving,route,constrained,road,algorithms,inefficient,this,paper,propose,novel,accelerated,namely,tackle,queries,networks,phases,efficiently,partition,entire,into,many,small,cells,grid,theoretically,prove,correctness,parallel,results,shifting,then,effective,multi,grained,pruning,technique,which,majority,can,be,without,further,checking,design,friendly,storage,structure,CRN,level,framework,compute,final,remaining,Finally,conduct,extensive,experiments,experimental,demonstrate,that,average,order,faster,than,state,competitors,maximum,speedup,achieve,about,times

0.596675