Research On Spatial Pattern Matching In Parallel Environment

In recent years,with the rapid development of mobile Internet and wireless communication technologies,location-based service applications continue to emerge.Users can obtain various convenient services through location and textual information.Behind these services,there are many effective algorithms to ensure the quality of their services.Therefore,spatial pattern matching with strong expressive ability has become a research hotspot.However,the current spatial pattern matching algorithm has two defects:On the one hand when dealing with spatial big data,the computational efficiency is still difficult to meet the actual requirements.On the other hand,the algorithm does not effectively filter the matching results,and a large number of matching results interfere with the user's choice,thus,it is not practical.In this paper,the problems of low efficiency and over-matching of current algorithms are improved from the aspects of computational framework and pattern matching filtering.Aiming at above problems,this paper first analyzes the current spatial pattern matching algorithm MSJ,and points out the reasons for the low efficiency and overmatching of MSJ.Then based on the parallel computing framework Spark,the spatial pattern matching algorithm PMSJ(Parallel Multi Star Join)and the Top-K SPM algorithm PIM(Parallel Incremental Matching)whose based on the parallel spatial pattern edge matching are designed.Those algorithms decomposes the spatial pattern matching problem into sub-problems called edge matching that can be executed independently and in parallel,and distributes the computational cost to each node in the cluster to improve the efficiency.Specifically PMSJ divides edge matching into two parallel steps: minimum bounding rectangle matching for spatial regions and edge matching for specific spatial objects,and prunes the result of minimum bounding rectangle matching before calculating edge matching to eliminate matching pairs those unable to compose a complete spatial pattern matching.PIM follows the idea of incremental matching,which run edge matching in parallel and gradually expands its search range.The experimental results on four real data sets show that the efficiency of the PMSJ algorithm is better than the current algorithms dealing with spatial big data.The efficiency of the PIM algorithm is also better than the baseline algorithm Top-K PMSJ proposed in this paper.At last,an interactive prototype system was developed based on the above two parallel algorithms.The system can intuitively display the query results of spatial pattern matching on the map.