Query-directed Probing Random-hyperplane LSH

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(MPLSH).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.This paper proposes an approach based on QDP sequence for cosine similarity search.Moreover,we give a set of complete theories and the corresponding proof for our method.In this paper,we conduct an experiment in which QDP-RHLSH and SWP-RHLSH are respectively adopted to demonstrate the superiority of our method.It is shown that the proposed QDP-RHLSH can achieve less probes and less query time than existing SWP-RHLSH.For reaching a desired recall,QDP requires less hash buckets than the existing algorithm.The most important is that our method just changes the search sequence,but not changes data structure in memory.It means that our method is not in conflict with the existing data structures.And it can be also directly used for a system where hash tables have been created.