Abstract: Approximate Nearest Neighbor (ANN) search has served as one of the most important technologies for efficient retrieval of large-scale data in the era of artificial intelligence. As a promising solution to the ANN, hashing has received a lot of attention due to its high efficiency and extensive works have been presented in the literature. However, so far, there is no work with attempt to comprehensively analyze and overview the state-of-the-art hashing methods. To address this, the basics of hashing, including distance calculation, loss function, discrete constraint and out-of-sample learning, are first systematically introduced. Then, the state-of-the-art hashing based methods are comparatively studied and experiments on the widely used databases are conducted to evaluate their performance. Finally, the key problems of hashing methods are summarized and some potential research directions are pointed out. It is believed that this endeavor could provide other researches with a useful guideline in designing effective and efficient hashing methods.

Key words: approximate nearest neighbor search, hashing learning, hashing, data retrieval