Locality sensitive hashing scheme based on online-learning.

Locally Sensitive Hashing (LSH) algorithms are classical algorithms commonly used on the c-Approximate Nearest Neighbor (c-ANN) search problem. When using Euclidean distance to measure sample similarity and solve the c-ANN problem, the traditional approach is to utilize the Exact Euclidean Locality Sensitive Hashing (E2LSH) algorithm based on the p-stable distribution. However, the uncertainty of the p-stable distribution causes the hash buckets constructed by the E2LSH algorithm to vary in queries. Therefore, this paper proposes the OLLSH algorithm based on the Weighted Majority algorithm in the Online-Learning framework, which selects the hash buckets with more stable query accuracy by weighted voting on the hash buckets generated by the E2LSH algorithm. Then, we conduct simulation experiments on synthetic dataset and four real data sets and conclude that the proposed OLLSH algorithm improves the accuracy compared to the original algorithm with the same memory usage. • The parameters of the E2LSH algorithm are analysed in detail. • The choice of hash buckets for the E2LSH algorithm is achieved with the WM algorithm. • The OLLSH algorithm saves memory by using less hash buckets during the query process. • The efficacy of the OLLSH algorithm was proved on both synthetic and real datasets. [ABSTRACT FROM AUTHOR]