MapReduce Algorithms for GIS Polygonal Overlay Processing
MapReduce Algorithms for GIS Polygonal Overlay Processing
复制标题
DOI：
10.1109/ipdpsw.2013.254
复制
发表时间：
2013-05
期刊：
影响因子：
--
通讯作者：
S. Puri;Dinesh Agarwal;Xi He;S. Prasad
中科院分区：
文献类型：
--
作者：
S. Puri;Dinesh Agarwal;Xi He;S. Prasad
多边形叠置是计算几何中的一种复杂运算。它在地理信息系统、计算机图形学、超大规模集成电路CAD等领域有着广泛的应用。针对该问题的顺序算法在文献中有很多，但缺乏分布式算法，特别是针对MapReduce平台的分布式算法。在GIS中，空间数据文件往往很大（以GB为单位），底层的叠加计算是高度不规则和计算密集型的。MapReduce范式现在是工业界和学术界处理大规模数据的标准。受MapReduce编程模型的启发，我们重新审视了分布式多边形覆盖问题及其在MapReduce平台上的实现。我们的算法是面向最大限度地提高本地处理和最大限度地减少MapReduce中洗牌和排序阶段固有的通信开销。我们已经对两个数据集进行了实验，并使用64个CPU内核实现了数据集1的22倍加速。
Polygon overlay is one of the complex operations in computational geometry. It is applied in many fields such as Geographic Information Systems (GIS), computer graphics and VLSI CAD. Sequential algorithms for this problem are in abundance in literature but there is a lack of distributed algorithms especially for MapReduce platform. In GIS, spatial data files tend to be large in size (in GBs) and the underlying overlay computation is highly irregular and compute intensive. The MapReduce paradigm is now standard in industry and academia for processing large-scale data. Motivated by the MapReduce programming model, we revisit the distributed polygon overlay problem and its implementation on MapReduce platform. Our algorithms are geared towards maximizing local processing and minimizing the communication overhead inherent with shuffle and sort phases in MapReduce. We have experimented with two data sets and achieved up to 22x speedup with dataset 1 using 64 CPU cores.