分布式并行计算环境下GML空间数据的划分策略及算法研究

发布时间：2019-01-01 21:49

【摘要】：GML具有简单性、半结构化、互操作性、开放性、通用性、灵活性等特点,因而在诸多领域得到了广泛应用。随着地理信息领域求解问题的不断拓展,所遇到的问题也越来越复杂,规模越来越大,传统GIS的空间数据存储与空间分析算法的效率优化和性能提升无法满足海量数据的存储与空间运算需求。利用分布式并行计算平台可以很好地解决这一问题。分布式并行系统的优劣很大程度取决于数据划分策略的好坏,而目前空间数据的划分方法没有考虑空间关联关系。因此针对一种适合GML空间数据的综合考虑负载平衡、邻近程度、面积平衡及空间关联关系的空间数据划分方法,本文取得了以下研究成果：第一,研究分析了基于Hilbert空间排列码的空间数据划分和基于K-平均聚类算法的空间数据划分两种算法的缺点。前者在保持各结点的空间数据所占范围平衡性上表现不佳,而后者则由于初始质心的不确定性导致划分结果不稳定。第二,结合Hilbert空间排列码和K-平均聚类算法,并综合考虑对象的空间关联关系提出一种新的GML数据划分算法。该算法考虑了各结点负载平衡、对象的邻近程度、面积平衡及对象间的空间关联关系。最后,根据提出的GML空间数据划分算法,分析设计了GML分布式存储系统,完成了基于Hadoop平台的分布式并行GML存储系统的数据划分模块。通过系统验证了数据划分算法的负载平衡性,并与Oracle Spatial和基于K-平均聚类的空间数据划分算法的并行加速比做了比较分析,与Hilbert码划分算法做了等分区域查询效率对比。结果表明,本划分算法拥有良好的负载平衡性和优秀的并行查询效率。
[Abstract]:GML is widely used in many fields because of its simplicity, semi-structure, interoperability, openness, versatility and flexibility. With the development of solving problems in the field of geographic information, the problems encountered are becoming more and more complex and larger. The efficiency optimization and performance improvement of the traditional spatial data storage and spatial analysis algorithm based on GIS can not meet the needs of massive data storage and spatial operation. Using distributed parallel computing platform can solve this problem well. The merits and demerits of distributed parallel systems depend to a great extent on the quality of data partitioning strategies, but the present spatial data partitioning methods do not take spatial association into account. Therefore, in view of a spatial data partition method which is suitable for GML spatial data, considering load balance, proximity degree, area balance and spatial correlation relationship, this paper has obtained the following research results: first, The shortcomings of spatial data partitioning based on Hilbert spatial permutation code and spatial data partitioning based on K-average clustering algorithm are studied and analyzed. The former is not good at maintaining the equilibrium of the spatial data of each node, while the latter is unstable because of the uncertainty of the initial centroid. Secondly, combining Hilbert spatial permutation code and K-average clustering algorithm, and considering the spatial correlation of objects, a new GML data partition algorithm is proposed. The algorithm takes into account the load balance of each node, the proximity of the object, the area balance and the spatial correlation between the objects. Finally, according to the proposed GML spatial data partition algorithm, the GML distributed storage system is analyzed and designed, and the data partition module of the distributed parallel GML storage system based on the Hadoop platform is completed. The load balance of the data partition algorithm is verified by the system, and the parallel speedup ratio of Oracle Spatial and spatial data partition algorithm based on K-average clustering is compared and compared with that of Hilbert code partition algorithm. The results show that the partition algorithm has good load balance and excellent parallel query efficiency.
【学位授予单位】：江西理工大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：P208;TP338.6

【参考文献】