Abstract:

The study of approximate k nearest neighbors query has attracted broad attention.Local sensitive hash is one of the mainstream ways to solve this problem.Local sensitive hash and its varients have noted the following problems:the uneven distribution of hashed data in the buckets,it cannot calculate the appropriate query range (for the parameter k) to build index.To tackle the above problem,a new data struct which called SLSB-forest was presented.The SLSB-forest combined the LSH and the B-tree to maintain the amount of bucket’s data in reasonable range.Two query algorithms were proposed:fast and accurate priority search.Theory and experimental results prove that query range can dynamic change during searching approximate k nearest neighbors.

Key words: approximate k nearest neighbor, locality sensitive hash, high dimensionality