System and method for agglomerative clustering

Abstract

An information handling system performs a method for finding a nearest neighbor of a point. In some embodiments, the method may be used for agglomerative clustering. The method includes projecting a space Θ of a first dimension with a first distance μ to a space P of a second, smaller dimension with a distance μ' by a projection function p. For all pairs of points vand vin Θ, μ′ (p(v), p(v))≤μ(v, v), where p is the function that projects points in Θ to points in P. The method also includes selecting a point v in Θ and performing a search for its nearest neighbor in Θ by projecting v to P and locating a set S of nearest neighbors in P of p(v). A search is then performed in Θ of a set of S′ of points that project onto the points in S.