In this paper, we propose a fast search method for asymmetric distance computation in large-scale binary 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. 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.

In this article, we propose a method of approximate asymmetric nearest-neighbor search for binary embedding codes. The asymmetric distance takes advantage of less information loss at the query side. However, calculating asymmetric distances through exhaustive search is prohibitive in a large-scale dataset. We present a novel method, called multi-index voting, that 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. In addition, a binary feature selection method based on minimal quantization error is proposed to address the memory insufficiency issue and improve the search accuracy. Substantial experimental evaluations were made to demonstrate that the proposed method can yield an approximate accuracy to the exhaustive search method while significantly accelerating the runtime. 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 exhaustive search method and accelerate the search by 73--128 times. It also demonstrates an excellent tradeoff between the search accuracy and time efficiency compared to the state-of-the-art nearest-neighbor search methods. Moreover, the proposed feature selection method shows its effectiveness and improves the accuracy up to 8.35% compared with other feature selection methods.

In this paper, we study the subsequence matching problem of near-duplicate video detection. In particular, we address the application of monitoring a continuous stream with a large video dataset. To achieve real-time response and high accuracy, we propose a novel framework containing two characteristics . First, the subsequence matching is transformed to a 2-D Hough space projection of pairwise frame similarities between two subsequences. We present an approximate Hough transform that replaces the 2-D Hough space with a 1-D Hough space. The near-duplicate subsequence detection can be deemed to be the voting and searching in the 1-D Hough space with a lower time complexity. Second, a coarse-to-fine matching strategy is incorporated in the proposed framework. The coarse level matching selects the candidate videos based on the time-decay hit frequency between the query stream and dataset videos. The fine level matching applies the approximate Hough transform to detect the near-duplicate subsequences coexisting within the query stream and candidate videos. Several state-of-the-art methods are implemented for comparison. Experimental results show our framework outperforms in terms of accuracy and efficiency.