Linear unsupervised hashing for ANN search in Euclidean space

详细信息    查看全文

• 作者：Jian WangAuthor Vitae ; Xin-Shun Xu ; ^{xuxinshun@sdu.edu.cn" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Shanqing GuoAuthor Vitae ; Lizhen CuiAuthor Vitae ; Xiao-Lin WangAuthor Vitae
• 关键词：Hashing ; ANN search ; Unsupervised Hashing ; Locality-Sensitive Hashing ; Sequential learning ; Euclidean space
• 刊名：Neurocomputing
• 出版年：2016
• 出版时间：1 January 2016
• 年：2016
• 卷：171
• 期：Complete
• 页码：283-292
• 全文大小：1680 K

文摘

Approximate nearest neighbors (ANN) search for large scale data has attracted considerable attention due to the fact that large amounts of data are easily available. Recently, hashing has been widely adopted for similarity search because of its good potential for low storage cost and fast query speed. Among of them, when semantic similarity information is available, supervised hashing methods show better performance than unsupervised ones. However, supervised hashing methods need explicit similarity information which is not available in some scenarios. In addition, they have the problems of difficult optimization and time consuming for training, which make them unpracticable to large scale data. In this paper, we propose an unsupervised hashing method – Unsupervised Euclidean Hashing (USEH), which learns and generates hashing codes to preserve the Euclidean distance relationship between data. Specifically, USEH first utilizes Locality-Sensitive Hashing (LSH) to generate pseudo labels; then, it adopts a sequential learning strategy to learn the hash functions, one bit at a time, which can generate very discriminative codes. Moreover, USEH avoids explicitly computing the similarity matrix by decomposing it into the product of a label matrix and its transposition, which makes the training complexity of USEH linear to the size of training samples when the number of training samples is much greater than the dimension of feature. Thus, it can efficiently work on large scale data. We test USEH on two large scale datasets – SIFT1M and GIST1M. Experimental results show that USEH is comparable to state-of-the-art unsupervised hashing methods.