Query-Directed Probing LSH for Cosine Similarity

Locality-sensitive hashing (LSH) considered as an efficient algorithm for large-scale similarity search has become increasingly popular. Recently, many of its variants have been applied widely in high-dimensional similarity search. To overcome the drawback of requirement for a large number of hash tables, researchers proposed the famous Multi-Probe LSH (MP-LSH). It has been used to improve the utilization of hash tables. There are two major probing sequences mentioned in MP-LSH, i.e., Step-Wise Probing (SWP) sequence and Query-Directed Probing (QDP) sequence. It is verified that QDP sequence is better than SWP sequence in number of probes and query time. However, the proposed QDP sequence is based on the E2LSH. It means that the method is only adopted for Euclidean distance. For cosine similarity, SWP sequence is still the only feasible method to perform Multi-Probe LSH.