Font Size: a A A

Research On Hashing Accelerated Approximate Nearest-Neighbor Search

Posted on:2016-01-01Degree:MasterType:Thesis
Country:ChinaCandidate:G M YangFull Text:PDF
GTID:2308330470963066Subject:Computer technology
Abstract/Summary:PDF Full Text Request
Nowadays, Nearest Neighbor Search becomes more and more important when facing the challenge of big data. Traditionally, to solve this problem, researchers mainly focus on building effective data structures (such as hierarchical k-means tree and nearest neighbor graph) or using hashing methods to accelerate the query process. In this paper, we propose a novel unified approximate nearest neighbor search scheme to combine the advantages of both the effective data structure and the fast Hamming distance computation in hashing methods. The proposed search scheme first uses hashing method to encode the data points, then adopts a two step ranking strategy to accelerate the search procedure of traditional nearest neighbor search methods. In this way, the searching procedure can be further accelerated. We further extend this idea and propose to combine hashing with hierarchical k-means tree and general graph structure. And to avoid the problem of local minimum in traditional graph nearest neighbor search methods, we introduce a relaxed stop condition and therefore have a longer search path. Experiments on several large scale and high dimensional data sets demonstrate the great superiority of the proposed framework compared with the state-of-the-art KNN search algorithms.
Keywords/Search Tags:Nearest Neighbor Search, Hashing, hierarchical k-means tree, Nearest Neighbor Graph
PDF Full Text Request
Related items