演講題目: Approximate Asymmetric Search for Binary Embedding Codes
演講者: 邱志義 國立嘉義大學資訊工程系
In this talk, we propose a method of approximate asymmetric nearest neighbor search for binary embedding codes. Asymmetric distances take advantage of less information loss at the query side. However, calculating asymmetric distances with the linear scan approach is prohibitive in a large-scale dataset. We present a novel algorithm called multi-index voting, which integrates the multi-index hashing technique with a voting mechanism, to select appropriate candidates and calculate their asymmetric distances. We show that the candidate selection scheme can be formulated as the tail of the binomial distribution function. Substantial experimental evaluations are given to demonstrate that, guided by the voting mechanism, the proposed method can yield an approximate accuracy to the linear scan approach while accelerating the run time with a significant speedup. For example, one result shows that in a dataset of one billion 256-bit binary codes, examining only 0.5% of the dataset can reach 95~99% close accuracy to the linear scan approach but can accelerate over 73~128 times.