Scene classification methods based on effective feature extraction and coding have obtained promising results in recent years. But the K-nearest neighbor search strategy in Locality-constrained Linear Coding (LLC) increases the complexity of the algorithm due to the exhaustive search. To solve the problem, an improved approximate nearest neighbor search strategy is proposed to improve the computational efficiency of LLC. Considering the mapping relationship between the visual words and features, a collaborative hashing method is incorporated to transform the high dimensional features into binary code form, and the original Euclidean space is transformed into the Hamming space that consists of multi similar features. The similar visual words can be queried quickly. Then the nearest neighbors can be searched efficiently through Hamming distance ranking, which can improve the coding efficiency. The experimental results on standard datasets demonstrate the effectiveness of the proposed approach, and the average classification accuracy can be improved.