基于Spark的并行反向k最近邻查询  

Parallel reverse k nearest neighbor query based on Spark

作　　者：杨泽雪 张毅[2] 李陆 刘伟东 蒋超 YANG Ze-xue;ZHANG Yi;LI Lu;LIU Wei-dong;JIANG Chao(College of Information and Computer Engineering,Northeast Forestry University,Harbin 150040,China;Department of Cooperation,Exchange,Innovation and Development,Heilongjiang Provincial Big Data Center of Government Affairs,Harbin 150028,China;Department of Computer Science and Technology,Heilongjiang Institute of Technology,Harbin 150050,China)

机构地区：[1]东北林业大学信息与计算机工程学院,黑龙江哈尔滨150040 [2]黑龙江省政务大数据中心合作交流与创新发展处,黑龙江哈尔滨150028 [3]黑龙江工程学院计算机科学与技术系,黑龙江哈尔滨150050

出　　处：《计算机工程与设计》2022年第12期3340-3347,共8页Computer Engineering and Design

基　　金：中国博士后科学基金项目(2019M651318);黑龙江省自然科学基金项目(LH2020F047);黑龙江省高等教育教学改革重点委托基金项目(SJGZ20200145);黑龙江工程学院创新团队基金项目(2020CX07)。

摘　　要：为提高海量空间大数据的反向k最近邻查询效率,采用当前流行的大数据处理框架Spark,对并行反向k最近邻查询进行研究。基于Spark框架构建并行索引结构,利用Voronoi图处理反向k最近邻查询的良好性能,构建基于网格和Voronoi图的双层索引结构;利用双层索引结构,给出高效的并行反向k最近邻查询的过滤精炼处理算法SV_RkNN,给出相关定理及证明。真实数据实验结果表明,所提SV_RkNN算法具有较高的查询效率。To improve the efficiency of reverse k nearest neighbor query for massive spatial big data,using the current popular big data processing framework Spark,parallel reverse k nearest neighbor query was researched.A parallel index structure was constructed based on Spark framework.The Voronoi diagram was used to process the good performance of the reverse k nearest neighbor query,and a two-layer index structure based on the grid and the Voronoi diagram was constructed.Using the index structure,an efficient parallel reverse k nearest neighbor filter and verification query processing method SV_RkNN was presented.Relevant theorems and proofs were given.Experimental results of real data show that the proposed SV_RkNN algorithm has higher query efficiency.

关 键 词：空间数据库 空间大数据 并行查询 反向k最近邻查询 VORONOI图 空间索引 网格 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]