The LSH (Locality Sensitive Hashing) method and its variants represent the state-of-the-art indexing techniques to process ANN (Approximate Nearest Neighbor) searches in a high dimensional data space.Although the existing LSH based techniques can efficiently deal with uniform distributed data

it is noticed from the principle of their design schemes that these techniques cannot handle non-uniform distributed data well.To tackle the above problem

this paper presents a new LSH based technique

called M2LSH (2 Layers Merging LSH)

to efficiently process ANN searches on non-uniform distributed data.The key idea is as follows.First

data objects are stored in a hash table with multiple buckets (i.e.

the first layer)

each of which corresponds to a combined hash vector used as its hash number.The count of data objects in each hash bucket is recorded.Secondly

using the hash functions for a second layer hash table

the bucket numbers from the first layer are projected into a one-dimensional space.In this space

some adjacent hash buckets from the first layer are merged so as to make the data objects uniformly distributed in the merged buckets at the second layer.Therefore

the M2LSH can not only improve the searching efficiency but also increase the accuracy of the search results.This paper also provides a detailed theoretical accuracy analysis for the M2LSH technique.Experiments using synthetic and real data show that the theoretical estimates are quite accurate

and the proposed M2LSH technique can efficiently process ANN searches with low false positive and negative rates.