The locality sensitive hashing (LSH) and its variants are efficient algorithms to solve the k nearest neighbor (kNN) search problems on high-dimensional data.However

with the increase of large data size

the traditional centralized LSH algorithms cannot meet the challenge of the big data era.Based on a new AND-OR construction

this paper proposes an algorithm (called C2SLSH) for the k nearest neighbor search on big data.Different to the traditional algorithms

the C2SLSH can directly get the results from an index without having to compare the original data.The theoretical analysis and experimental results show that the algorithm has stable scalability on a distributed platform.Furthermore

it is faster than the conventional methods for about three times with the same accuracy rate.