面向海量空间数据的分布式距离连接算法  

Distributed Distance Join Algorithm for Massive Spatial Data

作　　者：王如斌 李瑞远 何华均 刘通 李天瑞[1] WANG Ru-bin;LI Rui-yuan;HE Hua-jun;LIU Tong;LI Tian-rui(School of Information Science and Technology,Southwest Jiaotong University,Chengdu 611756,China;College of Computer Science,Chongqing University,Chongqing 400044,China;JD Intelligent Cities Research,Beijing 100176,China;School of Computer Engineering and Science,Shanghai University,Shanghai 200444,China)

机构地区：[1]西南交通大学信息科学与技术学院,成都611756 [2]重庆大学计算机学院,重庆400044 [3]京东智能城市研究院,北京100176 [4]上海大学计算机工程与科学学院,上海200444

出　　处：《计算机科学》2022年第1期95-100,共6页Computer Science

基　　金：国家重点研发计划(2019YFB2101801)。

摘　　要：空间距离连接是空间数据分析最基本的操作之一,具有广泛的应用场景。针对现有分布式方法的空间域选取过大、数据倾斜、自连接较慢的问题,提出了一种新的面向海量空间数据的分布式距离连接算法JUST-Join。首先,JUST-Join仅选取必要的空间区域作为全局域,能够提前过滤数据,减少无效的数据传输和不必要的计算开销;然后,同时考虑了参与连接的两个数据集的分布,从而缓解了数据倾斜问题;最后,针对自连接情形的冗余计算,采用平面扫描算法来进一步提高效率。文中使用Spark实现了JUST-Join算法,并利用真实的数据集做了大量实验。实验结果表明,JUST-Join算法在效率和扩展性方面都优于现有的最先进的分布式空间分析系统。Spatial distance join is one of the most common operations for spatial data analysis,which has various application scenarios.Existing distributed methods face the problems of too large space,high data skew,and slow self-join.To this end,this paper proposes a novel distributed distance join algorithm,i.e.,JUST-Join,for massive spatial data.First,JUST-Join regards only the necessary space as the global domain,which can filter invalid data out,reducing the overhead of unnecessary data transmission and computation.Second,we consider both the spatial distributions of the two datasets,which relieves the data skew issue.Third,for the spatial self-join,we adopt plane sweep method to further improve the efficiency.We implement JUST-Join algorithm based on Spark,and conduct extensive experiments using real datasets.The experimental results show that JUST-Join is superior to the state-of-the-art distributed spatial analysis systems in terms both of efficiency and scalability.

关 键 词：空间距离连接 空间分区 分布式计算 空间索引 时空数据 

分 类 号：TP338[自动化与计算机技术—计算机系统结构]