Finding k-Closest-Pairs Efficiently for High Dimensional Data.
Mario Alberto Lopez, Swanwa Liao · 2000
We present a novel approach to report approximate as well as exact k-closest pairs for sets of high dimensional points, under the L t -metric, t = 1; : : : ; 1. The proposed algorithms are efficient and simple to implement. They all use multiple shifted copies of the data points sorted according to their position along a space filling curve, such as the Peano curve, in a way that allows us to make performance guarantees and without assuming that the dimensionality d is constant. The first algorithm computes an O(d 1+1=t ) approximation to the k th closest pair distance in O(d 2 n log +dk(d + log k)) time. Experimental results, obtained using various real data sets of varying dimensions, indicate that the approximation factor is much better in practice. In the second algorithm we use this approximation in order to find the exact k closest pairs in O(dM) additional time, where M is the number of points in certain short subsegments of the space-filling curve. The exact algorithm is ...