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) |
| Number of Pages | 4 pages |
| Location | Fukuoka, Japan |
| Reviewed or 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. |
- Following files are available.
- Entry for BibTeX
@InProceedings{Mutoh2010, author = {Tomoyuki Mutoh and Masakazu Iwamura and Koichi Kise}, title = {Theoretical Analysis on Pruning Nearest Neighbor Candidates by Locality Sensitive Hashing}, booktitle = {Proc. 2010 IEEE Region 10 Conference (TENCON2010)}, year = 2010, month = nov, numpages = {4}, location = {Fukuoka, Japan} }