A k nearest neighbor patch match algorithm based on random match was proposed to solve the non-local similar patch search problem, which is an improvement of the patch match algorithm based on jump flooding. On the basis of the origin algorithm, the improved algorithm proposed an additional way to randomly generate candidate reference patch from the local neighborhood of each query patch, which raises the possibility of matching candidate patch to query patch and improves the matching accuracy. Experimental results show that the improved algorithm is comparable with the origin algorithm in time efficiency and parallelism, and outperforms the origin algorithm in matching accuracy.