Abstract: The kD tree is one of the most popular algorithms for searching the nearest neighbor,but its performance degrades quickly in high dimensional space.An overlap kD(okD) tree is proposed to address this problem,which can be used in high dimensional space.In the process of constructing the okD tree,overlaps are allowed between two child nodes,and these overlaps are not split and directly passed to the successors in the following partition procedure.In the process of traversing the okD tree,the nodes with overlap are not backtracked to improve the efficiency,and the overlaps in these nodes enlarge the search scale,which consequently improve the search accuracy.Experimental results show that the okD tree achieves a higher performance than other approximate kD tree algorithms.