Abstract: For the efficiency of the raster generation of Voronoi diagram on a planar point set composed of massive points, after its embarrassingly parallel abstract, this paper proposes the raster generation of Voronoi diagram based on the Euclidean distance. The algorithm is designed with three MapReduce Jobs. During the first MapReduce Job, the rasters are classified by the attached code. During the second MapReduce Job, the new data are classified according to its corresponding line number. During the third MapReduce Job, the partial Voronoi diagrams are generated in parallel, and they maintain a global order, then the final Voronoi diagram is generated by connecting the partial Voronoi diagrams. The experiments on different sizes of datasets on the Hadoop platform demonstrate that the algorithm under MapReduce shows good performance on speedup and scaleup.

Key words: Voronoi diagram, MapReduce, Hadoop platform, raster generation algorithm

摘要： 针对“海量”点组成的平面点集Voronoi图栅格生成算法的效率问题，对其进行易并行性抽象，提出了一种MapReduce模型下基于欧氏距离的Voronoi图栅格生成算法，该算法采用三个MapReduce Job来实现。在第一个MapReduce Job中，将栅格按照隶属代码进行归属分类。在第二个MapReduce Job中，将新数据按照其对应的行号进行归类。在第三个MapReduce Job中，并行生成全局有序的Voronoi图部分文件，并连接各个部分文件，生成最终的Voronoi图。在多个不同大小数据集上的实验结果表明，这种MapReduce模型下的算法部署在Hadoop集群上运行具有较好的加速比和扩展性。

关键词: Voronoi图, MapReduce, Hadoop平台, 栅格生成算法