基于密度的线数据分组算法研究

作者：魏海涛; 杜云艳; 许开辉; 吴笛; 易嘉伟; 莫洋; 刘张

来源：地球信息科学学报, 2015, 17(05): 538-546.

• 分而治之
• 并行计算
• 分布不均匀
• 线数据分组
• 负载均衡

目前,地理空间数据面临着由于数据量膨胀和计算量高速增长而引起算法效率低的问题,采用"分而治之"的数据分组策略提高运算效率已成为研究的热点。面向分布不均匀的线数据,本文提出了基于密度的线数据分组算法(简称LGAD)。首先,算法通过查找高密度区提取样本线段,保证了分组算法的起点落到高密区;其次,考虑线空间拓扑关系的复杂性,引用水平、垂直和夹角距离度量线段间距离,创建样本线段与其他线段的距离矩阵;最后,以距离矩阵和最优选择方法实现数据负载均衡分组。实验结果显示,对数据分组和分组后数据进行线段聚类的2个过程中,该算法体现了较好的时间优势,与串行计算相比,在分组数为2-12时,平均比率达4.3,提高了应用的响应速度,具有较好的实际意义。

• 单位
  中国科学院地理科学与资源研究所; 资源与环境信息系统国家重点实验室; 山东科技大学