基于不规则区域划分方法的k-Nearest Neighbor查询算法  

Irregular Partitioning Method Based k-Nearest Neighbor Query Algorithm Using Map Reduce

作　　者：张清清[1] 李长云[1] 李旭[1] 周玲芳[1] 胡淑新 邹豪杰[1] 

机构地区：[1]湖南工业大学计算机与通信学院,株洲412007

出　　处：《计算机系统应用》2015年第9期186-190,共5页Computer Systems & Applications

基　　金：2013年度国家科技部科技支撑计划(2013BAJ10B14-5);2014年湖南工业大学自然科学研究项目(2014HZX19)

摘　　要：随着越来越多的数据累积,对数据处理能力和分析能力的要求也越来越高.传统k-Nearest Neighbor(k NN)查询算法由于其容易导致计算负载整体不均衡的规则区域划分方法及其单个进程或单台计算机运行环境的较低数据处理能力.本文提出并详细介绍了一种基于不规则区域划分方法的改进型k NN查询算法,并利用对大规模数据集进行分布式并行计算的模型Map Reduce对该算法加以实现.实验结果与分析表明,Map Reduce框架下基于不规则区域划分方法的k NN查询算法可以获得较高的数据处理效率,并可以较好的支持大数据环境下数据的高效查询.With the constant accumulation of data, there is much higher desire for processing and analysis power to handle these data. Since the traditional k-Nearest Neighbor（k NN） query algorithm is easy to cause load imbalance on account of the regular partitioning method and its current platform is single process or single machine platform which cannot obtain high enough overall performance today, an irregular partitioning method based k NN algorithm is presented and being executed on the distributed parallel computing model which positioning to process large scale datasets in a distributed parallel way— Map Reduce in this paper. Experimental results and analysis show that the irregular partitioning method based k NN algorithm can realize much significant operational efficiencies and support efficient query of big data much better.

关 键 词：k-Nearest Neighbor(k NN)查询算法 不规则区域划分方法 MAP REDUCE 大数据 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]