Paper Info
Title
Warank: Weighted Asymmetric Ranking For Approximate Nearest Neighbor Search
Abstract
Binary hashing based methods have been widely used for large-scale approximate nearest neighbor search because of their two benefits: less memory usage and high search efficiency. In these methods, binary code ranking is usually implemented based on Hamming distance or asymmetric distance. Generally, asymmetric distance is more accurate than Hamming distance, thus recent work focuses on the asymmetric distance ranking. In existing asymmetric distance ranking, query-independent values are approximated by sample average values. However, when the distribution of data is not uniform, sample average values are not representative, leading to wrong ranking results. To address this problem, we propose Weighted Asymmetric Distance Ranking (WARank) algorithm which consists of two parts. First, we present an otsu threshold-based method to obtain more appropriate query-independent values in which the otsu threshold performs almost the same with the average value when the distribution of the data is uniform but much better when it is not uniform. Second, we present bit-level weight calculation method by which we can assign different weights to different bits in order to minimize the negative effect of any bit without uniform distribution. The experiments on public datasets show that the proposed WARank algorithm further increases the search accuracy compared to state-of-the-art methods.
Year
DOI
Venue
2015
10.1109/CIT/IUCC/DASC/PICOM.2015.43
CIT/IUCC/DASC/PICOM 2015 IEEE INTERNATIONAL CONFERENCE ON COMPUTER AND INFORMATION TECHNOLOGY - UBIQUITOUS COMPUTING AND COMMUNICATIONS - DEPENDABLE, AUTONOMIC AND SECURE COMPUTING - PERVASIVE INTELLIGENCE AND COMPUTING
Keywords
Field
DocType
Approximate Nearest Neighbor Search, Asymmetric Distance, Query-independent Values
Locality-sensitive hashing,Ranking,Pattern recognition,Best bin first,Binary code,Uniform distribution (continuous),Hamming distance,Artificial intelligence,Hamming weight,Mathematics,Nearest neighbor search
Conference
Citations 
PageRank 
References 
0
0.34
14
Authors
5
Name
Order
Citations
PageRank
Yuan Cao1112.86
Heng Qi221830.45
Keqiu Li31415162.02
Yingwei Jin46113.62
Zhi-yang Li514626.37