MapReduce Based Fast kNN Join
Dai Jia · Chinese Journal of Computers · 2015
kNN Join is a basic and important operation which is widely used in many fields.Hence,it plays a significant role in improving the efficiency of the applications in those fields.Nowadays,with the rapid increase of data size and the requirement for shorter response time(especially in some emergency environments),people actually ask for a more efficient way to conduct kNN Join.However,conventional kNN join operation is mostly running on single computer and/or single process at present,which cannot provide enough scalability.To address this problem,we incorporate the map-reduce framework into the running of kNN join and propose two novel methods:distributed sketched grid based kNN Join using map-reduce(DSGMP-J)and voronoi diagram based kNN Join using map-reduce(VDMP-J).And compare them with a stateof-the-art method:hadoop block nested loop join(H-BNLJ).The experiment results prove that the DSGMP-J and the VDMP-J outperform the H-BNLJ in scalability.