Japanese / English

Detail of Publication

Text Language English
Authors Tomoyuki Mutoh, Masakazu Iwamura and Koichi Kise
Title Theoretical Analysis on Pruning Nearest Neighbor Candidates by Locality Sensitive Hashing
Journal Proc. 2010 IEEE Region 10 Conference (TENCON2010)
Publisher IEEE Fukuoka Section
Reviewed or not Not reviewed
Month & Year November 2010
Abstract Locality Sensitive Hashing (LSH) is one of the most popular methods of the approximate near neighbor search. In applications that require the nearest neighbors of queries in a short time, LSH is sometimes used in pruning of the candidates of nearest neighbors. While the pruning reduces the processing time greatly, it also reduces the chances of retrieving the exact nearest neighbors. However, the pruning of nearest neighbor candidates using LSH has not been considered theoretically. Thus in this paper, we investigate the pruning effect by deriving the formulae of retrieval accuracy and computational cost of distance calculation for uniformly distributed data. Furthermore, we make evaluations on the formulae by comparison between simulation results and the theoretical values.
Back to list