Thumbnail
Access Restriction
Subscribed

Author Mutohy, T. ♦ Iwamura, M. ♦ Kise, K.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©2010
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Nearest neighbor searches ♦ Accuracy ♦ Computational efficiency ♦ Simulation ♦ Distributed databases ♦ Probability ♦ Educational institutions
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.
Description Author affiliation: Graduate School of Engineering, Osaka Prefecture University, 1-1 Gakuencho, Naka, Sakai, 599-8531 Japan (Mutohy, T.; Iwamura, M.; Kise, K.)
ISBN 9781424468898
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2010-11-21
Publisher Place Japan
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
e-ISBN 9781424468904
Size (in Bytes) 173.69 kB
Page Count 4
Starting Page 1027
Ending Page 1030


Source: IEEE Xplore Digital Library