Research On Key Technologies Of MaxRS Query Processing In Road Network

In smart phones,vehicles and wearable devices,GPS sensors are ubiquitous.They collect a lot of valuable spatial data from the real world.MaxRS query is an important query type on spatial data.It returns the position of the rectangle r in the huge data space,so as to maximize the weight of the points covered by r.The MaxRS query problem originates from the largest closed polygon problem,which is widely used in facility site selection and road planning.In recent years,it has attracted more and more researchers' attention.However,most of the existing researches focus on the Euclidean space,but the actual movement of the user is restricted by the road network,and the performance of existing MaxRS query on road network is poor.Based on this,this article studies the GPU-accelerated MaxRS query problem restricted by road network and S-MaxRS query problem restricted by road network with selection conditions.In the research of MaxRS query restricted by road network based on GPU acceleration,we first introduce the grid partition and shifting technology of road network,which theoretically proves the correctness of the query results.In order to process data efficiently,we design a GPU-friendly index,GRN-Index and two-level parallel query framework.After Grid is partitioned,multiple Cells are computed in parallel,so do multiple edges in the Cell,so as to make full use of GPU computing resources.Based on this,an efficient GAM algorithm is proposed.In order to further improve the query efficiency of the GAM algorithm,this paper proposes three pruning strategies(multi-level pruning).Through the relationship between the local optimal solution and the upper bound,unnecessary data is skipped to improve the query efficiency of the algorithm.Experiments show that the execution efficiency of the GAM algorithm is at least an order of magnitude higher than that of the SEG algorithm,and it can effectively calculate the MaxRS query results on the road network.In the research of S-MaxRS query on the road network,we first propose and define the S-MaxRS query problem,propose the BA algorithm as the baseline algorithm,and introduce the execution process of the BA algorithm.In order to solve the poor efficiency of the BA algorithm,this paper proposes a two-stage TSRN algorithm.The candidates generation stage uses pre-calculated FC-Lists to filter out edges that must not meet the user's selection needs,and the refinement stage accurately calculates the correct query results.This paper proposes two range pruning strategies.By calculating the coverage e-range,unnecessary edges and facilities are skipped to reduce computational overhead,thereby improving the query efficiency.Experiments show that the execution efficiency of the TSRN algorithm is about an order of magnitude relative to the BA algorithm,which can effectively calculate S-MaxRS query problems on the road network.