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

Parallel reverse k nearest neighbor query based on Spark

为提高海量空间大数据的反向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.