Fast nearest neighbor retrieval using randomized binary codes and approximate Euclidean distance

• We propose to approximate the Euclidean distance using the Hamming distance.
• The approximation relies on binary codes constructed from random projections.
• The approximation accuracy depends mainly on the number of projections.
• We also propose a fast retrieval method using the approximate distance.
• This method retrieves ranked result similar to the true Euclidean distance.

This paper investigates the use of binary codes in fast nearest neighbor retrieval for multi-dimensional dataset. The proposed method is based on a relation between the Euclidean distance and the Hamming distance between binary codes obtained from random projections of the two vectors. This relation allows approximating multi-dimensional Euclidean distance rapidly. The accuracy of the proposed approximation depends mainly on the length of the binary codes and not on the dimension of the input vector. Experimental results show that the proposed method yields an accurate approximation of the true distance. Fast search technique using the proposed distance is also presented. This technique is compared to other existing search methods. The experimental results are promising.