Entropy based locality sensitive hashing
Qiang Wang, Zhiyuan Guo, Gang Liu, Jun Hai Guo · 2012
Nearest neighbor problem has recently been a research focus, especially on large amounts of data. Locality sensitive hashing (LSH) scheme based on p-stable distributions is a good solution to the approximate nearest neighbor (ANN) problem, but points are always mapped to a poor distribution. This paper proposes a set of new hash mapping functions based on entropy for LSH. Using our new hash functions the distribution of mapped values will be approximately uniform, which is the maximum entropy distribution. This paper also provides a method on how these parameters should be adjusted to get better performance. Experimental results show that the proposed method will be more accurate with the same time consuming.