Paper Info
Title
An effective method for approximating the euclidean distance in high-dimensional space
Abstract
It is crucial to compute the Euclidean distance between two vectors efficiently in high-dimensional space for multimedia information retrieval. We propose an effective method for approximating the Euclidean distance between two high-dimensional vectors. For this approximation, a previous method, which simply employs norms of two vectors, has been proposed. This method, however, ignores the angle between two vectors in approximation, and thus suffers from large approximation errors. Our method introduces an additional vector called a reference vector for estimating the angle between the two vectors, and approximates the Euclidean distance accurately by using the estimated angle. This makes the approximation errors reduced significantly compared with the previous method. Also, we formally prove that the value approximated by our method is always smaller than the actual Euclidean distance. This implies that our method does not incur any false dismissal in multimedia information retrieval. Finally, we verify the superiority of the proposed method via performance evaluation with extensive experiments.
Year
DOI
Venue
2006
10.1007/11827405_84
DEXA
Keywords
Field
DocType
euclidean distance,effective method,high-dimensional space,large approximation error,approximation error,actual euclidean distance,estimated angle,previous method,additional vector,multimedia information retrieval
Euclidean domain,Magnitude (mathematics),Feature vector,Minkowski distance,Effective method,Computer science,Euclidean distance,Algorithm,Approximation error,Euclidean distance matrix
Conference
Volume
ISSN
ISBN
4080
0302-9743
3-540-37871-5
Citations 
PageRank 
References 
6
0.82
10
Authors
4
Name
Order
Citations
PageRank
Seungdo Jeong1258.82
Sang-Wook Kim2792152.77
Kidong Kim3212.26
Byung-Uk Choi45014.62