Full Citation

Title: Convergent Bounds on the Euclidean Distance

Citation Type: Miscellaneous

Publication Year: 2011

ISBN:

ISSN:

DOI:

NSFID:

PMCID:

PMID:

Abstract: Given a set V of n vectors in d-dimensional space, we provide an efficient method for computing quality upper and lower bounds of the Euclidean distances between a pair of vectors in V . For this purpose, we define a distance measure, called the MS-distance, by using the mean and the standard deviation values of vectors in V. Once we compute the mean and the standard deviation values of vectors in Vin O(dn) time, the MS-distance provides upper and lower bounds of Euclidean distance between any pair of vectors in V in constant time. Furthermore, these bounds can be refined further in such a way to converge monotonically to the exact Euclidean distance within d refinement steps. An analysis on a random sequence of refinement steps shows that the MS-distance provides very tight bounds in only a few refinement steps. The MS-distance can be used to various applications where the Euclidean distance is used to measure the proximity or similarity between objects. We provide experimental results on the nearest and the farthestneighbor searches.

User Submitted?: No

Authors: Ahn, Hee-Kap; Hwang, Yoonho

Publisher: Pohang University of Science and Technology

Data Collections: IPUMS USA

Topics: Other

Countries: