7.3.1 顶点层次结构构建结果及分析
基于Spark的分布式内存计算平台,利用B-DP算和VW算法构建空间对象的顶点层次结构构建等预处理工作,以提高数据处理的性能。顶点层次结构的构建等预处理工作主要包括三项:一是线对象的顶点误差计算与线对象所对应的二叉树的生成与存储;二是线对象连接形成的组合对象的顶点误差计算及其所对应的二叉树的生成与存储;三是为加速窗口查询而进行的顶点层次化空间索引四叉树的生成与存储。实验采用OpenStreet Map对全球海岸线数据、大不列颠岛与爱尔兰岛上全要素数据进行分析。
1.全球海岸线数据实验结果分析
针对全球海岸线数据,本节基于B-DP算法与VW算法,分别从线对象的顶点误差计算与线对象所对应的二叉树构建、组合对象的顶点误差计算及其所对应的二叉树的构建、顶点层次化空间索引四叉树索引的构建三个方面的时间消耗进行结果分析,同时,对比分析了4个与8个节点数量下BDP算法与VW算法的性能,如表7-11～表7-13所示。
表7-11 基于B-DP与VW算法的线对象顶点误差计算
表7-12 基于B-DP与VW算法的组合对象顶点误差计算
表7-13 基于B-DP与VW算法的索引构建
(1)基于B-DP与VW算法的线对象顶点误差计算
如图7-4所示,依次记录从1万到8万个线对象进行B-DP算法处理并构建二叉树的时间,不同线性的线条表示依次在1～8个计算节点上分配计算任务时所花费的时间。从图中可以看出,随着计算节点数量的增加,处理时间逐渐减少,充分体现了分布式对于提升效率的作用。同时,在计算任务较低时,由于任务启动或其他方面原因,即使增加节点数量也没有大尺度的减少处理时间,但随着任务量增加,增加节点产生的效果越来越明显。
图7-4 基于B-DP算法的线对象顶点误差计算
如图7-5所示,依次记录从1万到8万个线对象进行VW算法处理并构建二叉树的时间,不同线型的线条表示依次在1～8个计算节点上分配计算任务时所花费的时间。从图中可以看出,随着计算节点数量的增加,处理时间逐渐减少,充分体现了分布式对于提升效率的作用。
图7-5 基于VW算法的线对象顶点误差计算
(2)基于B-DP算法与VW算法的组合对象顶点误差计算
如图7-6所示,依次记录从0.2万到1.6万个组合对象进行B-DP算法处理并构建二叉树的时间,不同线型的线条表示依次在1～8个计算节点上分配计算任务后该处理所花费的时间。从图中可以看出,随着计算节点数量的增加,处理时间逐渐减少,表明分布式计算提升了数据预处理效率,当然这种提升速度低于计算节点增加的速度。同时由于一些随机因素的影响,当计算任务的分布程度较低时,计算任务的时间具有一定的不稳定性,即在某些情形下时间较长。
如图7-7所示,依次记录从0.2万到1.6万个组合对象进行B-DP算法处理并构建二叉树的时间,不同线型的线条表示依次在1～8个计算节点上分配计算任务后该处理所花费的时间。从图中可以看出,随着计算节点数量的增加,处理时间逐渐减少,表明分布式计算提升了数据预处理效率,当然这种提升速度低于计算节点增加的速度。同时由于一些随机因素的影响,当计算任务的分布程度较低时,计算任务的时间具有一定的不稳定性,即在某些情形下会较长时间。
图7-6 基于B-DP算法的组合对象顶点误差计算
图7-7 基于VW算法的组合对象顶点误差计算
(3)基于B-DP算法与VW算法的顶点层次结构索引构建
如图7-8所示,依次记录从500万到4 000万个顶点进行层次结构空间索引构建的时间,不同线型的线条表示依次在1～8个计算节点上分配计算任务后处理所花费的时间。图中结果显示随着计算节点数量的增加,层次结构构建所用时间逐渐减少,表明分布式计算提升了处理效率。同时其提升速度低于计算节点增加的速度。
图7-8 基于B-DP算法的顶点层次结构索引构建
如图7-9所示,依次记录从500万到4 000万个顶点进行层次结构空间索引构建的时间,不同的线条表示依次在1～8个计算节点上分配计算任务后该处理所花费的时间。图中结果显示随着计算节点数量的增加,空间索引构建所用时间逐渐减少,表明分布式计算提升了处理效率。同时其提升速度低于计算节点增加的速度。
(4)基于B-DP与VW算法的顶点误差计算及顶点层次结构索引构建比较
如图7-10所示,依次记录从1万到8万个顶点进行B-DP和VW算法处理并构建二叉树的时间,不同线型的线条表示依次在4个、8个计算节点上分配计算任务后该处理所花费的时间。图中结果显示无论是B-DP算法还是VW算法,节点数量增加,处理时间逐渐减少,表明分布式计算提升了数据预处理效率;在节点数量相同且数量为4时,在顶点小于65 000时,VW算法耗费时间高于B-DP算法,但在大于65 000时,B-DP算法耗费时间高于VW算法,顶点数量达到8万时,B-DP算法耗费时间略高于VW算法;而在结点数量为8个时,两条线多次交叉,说明两种算法耗费时间有高有低,没有可遵循的规律。
图7-9 基于VW算法的层次结构索引构建(https://www.daowen.com)
如图7-11所示,依次记录从0.2万到1.6万个组合对象进行B-DP与VW算法处理并构建二叉树的时间,不同线型的线条表示依次在4个和8个计算节点上分配计算任务后该处理所花费的时间。从图中可以看出,无论B-DP算法还是VW算法,节点数量由4个增加到8个,组合对象的顶点分布式误差测定时间减少;在节点数目相同且均为4时,开始VW算法耗费时间多于B-DP算法,后两者耗费相同,最终VW算法耗费时间多于B-DP算法;在节点数目为8时,B-DP或VW算法耗费时间变化不大。
图7-10 基于B-DP算法与VW算法的线对象顶点误差计算比较
图7-11 基于B-DP算法与VW算法的组合对象误差计算比较
如图7-12所示,依次记录从500万到4 000万个顶点B-DP算法与VW算法进行带有误差的层次结构空间索引构建的时间,不同线型的线条表示依次在4个和8个计算节点上分配计算任务后该处理所花费的时间。图中结果显示无论B-DP算法还是VW算法,节点数量由4个增加到8个,空间索引构建所用时间逐渐减少,表明分布式计算提升了处理效率;在节点数目相同且均为4时,VW算法构建误差索引耗费时间多于B-DP算法;在节点数目为8时,两种算法耗费时间基本保持一致。
图7-12 基于B-DP算法与VW算法的顶点层次结构索引构建比较
2.大不列颠岛及爱尔兰岛数据实验结果分析
针对大不列颠岛及爱尔兰岛的全要素矢量数据,本节基于B-DP算法与VW算法,分别从线对象、组合对象进行顶点误差计算与层次结构构建,其次,挑选了道路网与边界线两类数据开展顶点误差计算与层次结构构建,从四个方面的时间消耗进行结果分析。
(1)基于B-DP算法与VW算法的线对象顶点误差计算
如图7-13所示,依次记录从144万到1 152万个线对象进行B-DP算法处理并构建二叉树的时间,不同线型的线条表示依次在1～8个计算节点上分配计算任务时所花费的时间。从图中可以看出,随着计算节点数量的增加,处理时间逐渐减少,充分体现了分布式对于提升效率的作用。同时,在计算任务较低时,由于任务启动或其他方面原因,即使增加节点数量也没有大尺度的减少处理时间,但随着任务量增加,增加节点产生的效果越来越明显,在节点数为1时,耗费时间变化较大,可能与任务量的复杂性有关。
图7-13 基于B-DP算法的线对象顶点误差计算
如图7-14所示,依次记录从144万到1 152万个线对象进行VW算法处理并构建二叉树的时间,不同线型的线条表示依次在1～8个计算节点上分配计算任务时所花费的时间。从图中可以看出,随着计算节点数量的增加,处理时间逐渐减少,充分体现了分布式对于提升效率的作用。同时,在计算任务较低时,由于任务启动或其他方面原因,即使增加节点数量也没有大尺度的减少处理时间,但随着任务量增加,增加节点产生的效果越来越明显。
如图7-15所示,依次记录从144万到1 152万个英国线对象进行B-DP与VW算法处理并构建二叉树的时间,不同线型的线条表示依次在4个和8个计算节点上分配计算任务后该处理所花费的时间。从图中可以看出,无论B-DP算法还是VW算法,节点数量由4个增加到8个,线对象耗费时间减少,体现了分布式的作用,同时B-DP算法耗费时较少,效率较高。
(2)基于B-DP与VW算法的组合对象顶点误差计算
如图7-16所示,依次记录47 500个的多边形进行B-DP与VW算法处理并构建二叉树的时间,不同线型的线条表示依次在1～8个计算节点上分配计算任务时所花费的时间。图中可以看出,随着节点数的增加,多边形耗费的时间下降趋势,但在节点为4时出现上升,进而又呈现下降趋势,体现了分布式的作用,同时相同节点数情况下,B-DP算法与VW算法相比,BDP算法耗费时较少,效率较高。
图7-14 基于VW算法的线对象顶点误差计算
图7-15 基于B-DP算法与VW算法的线对象顶点误差计算比较
图7-16 基于B-DP算法与VW算法的组合对象顶点误差计算
(3)基于B-DP与VW算法的道路网顶点误差计算
如图7-17所示,依次记录10 640个道路网进行B-DP与VW算法处理并构建二叉树的时间,不同线型的线条表示依次在1～8个计算节点上分配计算任务时所花费的时间。图中可以看出,随着节点数的增加,道路网耗费的时间整体呈现下降趋势,体现了分布式计算的高效性。相同处理节点数目情况下,B-DP算法与VW算法相比,在1～4个节点时,两者耗费时间相差不大,无规律可循,5～8个节点时,B-DP算法耗费时间较短,效率较高。
(4)基于B-DP与VW算法的边界线顶点误差计算
如图7-18所示,依次记录65 924个边界线进行B-DP与VW算法处理并构建二叉树的时间,不同线型的线条表示依次在1～8个计算节点上分配计算任务时所花费的时间。图中可以看出,随着节点数的增加,边界线耗费的时间整体呈现下降趋势,体现了分布式计算的高效性。相同处理节点数目情况下,B-DP算法与VW算法相比,在1～3个节点时,两者耗费时间有一定差距,之后随着节点数增多,B-DP算法与VW算法耗费时间相差不大。
图7-17 基于B-DP算法与VW算法的道路网顶点误差计算
图7-18 基于B-DP算法与VW算法的边界线顶点误差计算
