计算机工程

• 先进计算与数据处理 • 上一篇    下一篇

基于KD树划分的云计算DBSCAN优化算法

陈广胜1,2,程逸群1,2,景维鹏1,2   

  1. (1.东北林业大学 信息与计算机工程学院,哈尔滨 150040;2.黑龙江省林业生态大数据存储与高性能(云)计算工程研究中心,哈尔滨 150040)
  • 收稿日期:2016-03-18 出版日期:2017-04-15 发布日期:2017-04-14
  • 作者简介:陈广胜(1969—),男,教授、博士,主研方向为大数据存储、云计算;程逸群,硕士研究生;景维鹏,副教授、博士。
  • 基金项目:
    黑龙江省自然科学基金重点项目(ZD201403);林业公益性行业科研专项(201504307)。

DBSCAN Optimization Algorithm Based on KD-tree Partitioning in Cloud Computing

CHEN Guangsheng  1,2,CHENG Yiqun  1,2,JING Weipeng  1,2   

  1. (1.College of Information and Computer Engineering,Northeast Forestry University,Harbin 150040,China; 2.Heilongjiang Province Engineering Technology Research Center for Forestry Ecological Big Data Storage and High Performance(Cloud) Computing,Harbin 150040,China)
  • Received:2016-03-18 Online:2017-04-15 Published:2017-04-14

摘要: 在并行RDD-DBSCAN算法的数据划分和区域查询过程中会对数据集进行重复访问,降低了算法效率。为此,提出基于数据划分和融合策略的并行DBSCAN算法(DBSCAN-PSM)。利用KD树进行数据划分,实现数据分区与区域查询步骤的合并,从而减少数据集的访问次数以及降低I/O过 程对算法效率的影响。采用判定数据点自身属性的方式,对标注为边缘点的数据进行融合,避免全局标记的额外时间开销。实验结果表明,DBSCAN-PSM算法相比RDD-DBSCAN算法可节省18%左右的运行时间,适用于处理海量数据聚类问题。

关键词: 聚类, DBSCAN算法, Spark平台, 数据划分, 数据融合

Abstract: The parallel RDD-DBSCAN algorithm has a repeated access to the data set in the data partition and region query steps,which reduces the efficiency of the algorithm.Aiming at the above problems,a parallel DBSCAN algorithm based on data partitioning and fusion stragy(DBSCAN-PSM) is proposed.It imports the KD-tree to partition the data,merges the partition and region query steps,reduces the number of access to the data set and decreases the influence of I/O on the algorithm.Data fusion method is realized by determining the clustering characteristics of the spatial boundary points,which avoids the time overhead of global markup.Experimental results show that DBSCAN-PSM algorithm runs faster than RDD-DBSCAN by 18%.It can deal with mass data clustering problem more effectively.

Key words: clustering, DBSCAN algorithm, Spark platform, data partitioning, data fusion

中图分类号: