Design And Application Of Parallel Voronoi Diagram Parallel Algorithm Based On MapReduce

Voronoi is a basic data structure classifying space by distance, which reflects an ideal state for all the generators, but in reality the impact field of generator is affected by many different factors, so in order to take the impact factors of generators into account, we need to assign the weight for generators, thus leading to a weighted Voronoi diagram(WVD).The generation of the WVD appeals to be Vector Method and Raster Method. The Vector Method has a good accuracy, but its data structures complicatedly and has difficulties in dealing with linear and area generator. When facing vast and complex geography data, Vector Method does not satisfy the need. However, Raster Method owns the limited accuracy; it can be used for the construction of different generators, and good at processing the complex spiral entity. Moreover, map data tends to be more large-scale and more considerable, and the serial Raster Method is not so efficient, on the countrary, the parallel process provides an efficient improvement and optimization for Raster Method.The traditional Voronoi diagram parallel method is offen based on parallel environment such as MPI, OpenMP, GPU, which generatesVoronoidiagram efficiently, but limited by the bottom-layer configuarition and implementation detail, while the open cloud platform Hadoop simplifies the design for the distributed program, improves the computing performance, and solves the large-scale map data computing problem of Voronoi diagram benefiting from its high-reliable, high-efficient, well-scalable, and the ablility to deploy on the cheap hardware.Therefore, This paper has a deep research on the parallel generating algorithm and its application in the MapReduce model, this paper mainly include:(1) Demostration for the Weighted Voronoi Diagram about the basic concept, application, generating algorithm etc, and a discussion about the correlative technique of Hadoop platform, which underlines the future study theoretically.(2) Against the low efficient drawback of the traditional Weighted Voronoi Diagram raster generating algorithm, this paper proposed a kind of generating algorithm of the parallel raster weighted Voronoi diagram based on MapReduce, and also verified the speedup and the scalablity of the proposed algorithm on Hadoop platform. (3) The paper apply Weighted Voronoi Diagram in the situation of supermarket recommendation and planning layout of sewage treatment plant. As to the supermarket recommendation, we show a way of determining weight by considering various user assessmeng index, exemplified by the supermarket custom assessment data of the Public Scoring Web, applied with the weighted Voronoidiagram, and recommend the optimum large-scale comprehensive supermarket for the customs. As for the planning layout of the sewage treatment plant, the model for defining the responsible areas of Sewage treatment plant based on weighted Voronoi diagram was built by introducing the "scale" parameter in the breaking-point model into weighted Voronoi diagram, raising reference for these plants.