摘要
目前,地理空间数据面临着由于数据量膨胀和计算量高速增长而引起算法效率低的问题,采用"分而治之"的数据分组策略提高运算效率已成为研究的热点。面向分布不均匀的线数据,本文提出了基于密度的线数据分组算法(简称LGAD)。首先,算法通过查找高密度区提取样本线段,保证了分组算法的起点落到高密区;其次,考虑线空间拓扑关系的复杂性,引用水平、垂直和夹角距离度量线段间距离,创建样本线段与其他线段的距离矩阵;最后,以距离矩阵和最优选择方法实现数据负载均衡分组。实验结果显示,对数据分组和分组后数据进行线段聚类的2个过程中,该算法体现了较好的时间优势,与串行计算相比,在分组数为2-12时,平均比率达4.3,提高了应用的响应速度,具有较好的实际意义。
Parallel computing provides a promising solution to accelerate complicated spatial data processing, which is becoming increasingly computational intense. Partitioning large datasets into workload-balanced sub- groups remains a challenge, particularly for unevenly distributed spatial data. In this study, a density-based data grouping algorithm was developed to tackle the partition problem for large line data. The algorithm includes three procedures: (1) extracting representative segment samples based on data density distribution; (2) generating a distance matrix between segment samples and the rest of the data by using three line distance measurements into calculations; (3) grouping line segments with data load balanced. Experiments show that the algorithm is able to partition large line data efficiently and evenly into equally sized sub-groups. The speed-up ratios of parallel interpo- lation save up to 65% of the execution time in comparison with consequential interpolation. A high efficiency of par- allel computing was achieved when the datasets were divided into an optimal number of child data groups.
出处
《地球信息科学学报》
CSCD
北大核心
2015年第5期538-546,共9页
Journal of Geo-information Science
基金
海洋公益性专项项目"海洋环境信息云计算与云服务体系框架应用研究"(201105033)
海洋预报综合信息系统(Mi FSIS)研究应用项目(201105017)
关键词
分而治之
并行计算
分布不均匀
线数据分组
负载均衡
divide and rule
parallel computing
unevenly distributed data
line segments
balanced workloads