Boundary-expanding locality sensitive hashing

Locality sensitive hashing (LSH) has been introduced as an indexing structure for fast large-scale data retrieval. A significant drawback of this technique is that a large number of hash functions require lots of hash computation time. To resolve this issue, the paper presents a new index construction algorithm called boundary-expanding LSH, where the boundary of each bucket is expanded so that each point may be mapped to multiple adjacent buckets in each hash table. The proposed algorithm can map points near to the two sides of the boundary into the same bucket, which increases the collision probability of neighbors. To achieve the same search accuracy, boundary-expanding LSH needs fewer hash tables and less hash computation time, so it can provide us a higher acceleration factor. To obtain the best performance, the paper also presents a parameter optimization method. Experiments conducted on two audio databases show its efficiency.