并行环境下的空间模式匹配  

Spatial pattern matching in parallel environment

作　　者：邓涛 陈红梅[1] 王丽珍[1] Deng Tao;Chen Hongmei;Wang Lizhen(School of Information Science and Engineering,Yunnan University,Kunming,650504,China)

机构地区：[1]云南大学信息学院,昆明650504

出　　处：《南京大学学报（自然科学版）》2021年第2期279-288,共10页Journal of Nanjing University（Natural Science）

基　　金：国家自然科学基金(61662086,61966036);云南省创新团队项目(2018HC019)。

摘　　要：空间模式匹配在各类基于位置的服务中有广泛的应用,但在面向空间大数据时,现有空间模式匹配算法的效率难以满足实际要求.针对上述问题,采用并行计算框架Spark,设计基于空间模式边匹配并行的空间模式匹配算法PMSJ(Parallel Multi Star Join).PMSJ算法将空间模式匹配问题分解为可以独立、并行执行的称为边匹配的子问题,将计算量分散至集群中各个计算节点以提高计算效率.具体地,PMSJ将边匹配分为针对空间区域的最小边界矩形匹配与针对具体空间对象的边匹配两个并行步骤,并在计算边匹配前对最小边界矩形匹配的结果进行剪枝,排除无法产生完整空间模式匹配的匹配对.在四个真实数据集上的实验结果表明,在面向空间大数据时,PMSJ算法的效率优于现有算法.Spatial pattern matching is widely used in various location⁃based services.However,when dealing with large spatial big data,the computational efficiency is still difficult to meet the actual requirements.Aiming at above problems,this paper proposes to use the parallel computing framework Spark to design a spatial pattern matching algorithm PMSJ(Parallel Multi Star Join)based on parallel spatial pattern edge matching.The PMSJ algorithm 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.The experimental results on four real data sets show that the efficiency of PMSJ algorithm is better than existing algorithms when facing spatial big data.

关 键 词：空间模式 空间模式匹配 MAPREDUCE SPARK 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]