A GPU Friendly Algorithm And Application For Point Recognition Within Arbitrary Number Of Arbitrary Shaped Query

The problem of identifying point sets inside arbitrary multiple arbitrary polygons is used to answer what data points are available within arbitrary multiple query regions,often as a first step in the exploration of spatial data,and can serve a wide range of downstream tasks,such as social media,weather warning systems,carpooling programs,etc.,and has a significant impact on the rapid response of these services.However,point set recognition inside arbitrary polygons often includes computationally intensive detection of points inside polygons,which challenges the responsiveness of recognition algorithms.This challenge is further complicated by the proliferation of spatial data caused by the widespread use of low-cost sensors.Existing solutions for the recognition of point sets inside arbitrary polygons typically have two main drawbacks.First,the solutions are usually tightly coupled to the type of query polygon,which makes them difficult to adapt to other types of queries;second,the time complexity of these solutions to perform queries is usually closely related to the number of polygons and cannot achieve better performance on queries with multiple polygons.The performance of graphics processors has been increasing in recent years,and using the powerful computational performance of graphics processors to enhance the efficiency of computationally intensive tasks provides a new idea for the above problems.Accordingly,this paper designs a graphics processor-friendly algorithm for point set recognition inside any multiple arbitrary polygons,converts the determination of points inside a polygon into a set of drawing operations on the canvas,and uses the graphics processor’s rendering pipeline to achieve interactive response times.Also,this paper designs a data encoding to implement the function of recording multiple data information on the same pixel block.In addition,the performance of the algorithm is analyzed theoretically in this paper,including time com-plexity,tightness of the encoding,and error control range.In this paper,we apply the above algorithms to a typical downstream task,a location-based influence maximization service,and develop a prototype system nameda~2Reg Inf.The system contains a pair of adaptive so-lutions called GPU-Reg Inf and Ray-Reg Inf and both support queries for arbitrary multiple arbitrary polygons.In particular,the former solution is efficient when the number of query regionsis small,while the latter pair is-insensitive and thus performs better whenis large.In this paper,the GPU-friendly arbitrary polygon interior point set recognition algorithm GPU-Reg is proposed to eliminate the limitation of the traditional solution on the number of query regions as well as their shapes.Meanwhile,this paper conducted an experimental study of the proposed GPU-Reg algorithm using two real social network datasets of different sizes.After setting the relevant parameters,it is compared with the existing benchmark algo-rithm in terms of running time to verify the performance advantages of this paper’s scheme.Experiments are conducted using multiple polygons to verify that the scheme is effective un-der arbitrary polygon regions.Experiments using multiple polygons are conducted to verify the scalability of the scheme.