Title :
Boundary-expanding locality sensitive hashing
Author :
Qiang Wang ; Zhiyuan Guo ; Gang Liu ; Jun Guo
Author_Institution :
Pattern Recognition & Intell. Syst. Lab., Beijing Univ. of Posts & Telecommun., Beijing, China
Abstract :
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.
Keywords :
audio databases; optimisation; probability; acceleration factor; audio databases; boundary expanding LSH; boundary expanding locality sensitive hashing; collision probability; hash computation time; hash functions; hash table; index construction algorithm; indexing structure; large scale data retrieval; multiple adjacent bucket; parameter optimization method; Acceleration; Accuracy; Feature extraction; Indexes; Optimization; Pattern recognition; Speech; Locality sensitive hashing (LSH); approximate nearest neighbor (ANN); information retrieval; large-scale;
Conference_Titel :
Chinese Spoken Language Processing (ISCSLP), 2012 8th International Symposium on
Conference_Location :
Kowloon
Print_ISBN :
978-1-4673-2506-6
Electronic_ISBN :
978-1-4673-2505-9
DOI :
10.1109/ISCSLP.2012.6423463