Abstract: kNN join is a frequently used operation in spatial database.It involves both the join and the NN search.Data scale is exploding,and traditional centralized algorithm can not meet the requirements.It is an urgent problem to design distributed kNN join algorithm currently.Existing distributed algorithms include several rounds of serial MapReduce tasks,but each MapReduce task reads and writes data from distributed file system.It is inefficient when expressing dependencies between jobs,and these algorithms are inefficient.Firstly,we proposed a framework based on data stream on MapReduce.This framework models data handle process according to the data flow diagram,and we proposed an efficient kNN join algorithm on the framework.The algorithm maps multi-dimensional data sets into one dimension using space-filling curves (z-values),and transforms kNN joins into a sequence of one-dimensional range searches.Experimental results demonstrate that the algorithm can efficiently resolve the large scale kNN join spatial query.

Key words: kNN join,Data stream,MapReduce,Framework