DSH: Data Sensitive Hashing for High-Dimensional k-NN Search

The need to locate the k-nearest data points with respect to a given query point in a multi- and high-dimensional space is common in many applications. Therefore, it is essential to provide efficient support for such a search. Locality Sensi-tive Hashing (LSH) has been widely accepted as an effective hash method for high-dimensional similarity search. Howev-er, data sets are typically not distributed uniformly over the space, and as a result, the buckets of LSH are unbalanced, causing the performance of LSH to degrade. In this paper, we propose a new and efficient method called Data Sensitive Hashing (DSH) to address this draw-back. DSH improves the hashing functions and hashing fam-ily, and is orthogonal to most of the recent state-of-the-art approaches which mainly focus on indexing and querying s-trategies. DSH leverages data distributions and is capable of directly preserving the nearest neighbor relations. We show the theoretical guarantee of DSH, and demonstrate its efficiency experimentally