Finding k-Closest-Pairs Efficiently for High Dimensional Data

We present a novel approach to report approximate aswell as exact k-closest pairs for sets of high dimensionalpoints, under the L t -metric, t = 1; : : : ; 1. The proposedalgorithms are efficient and simple to implement.They all use multiple shifted copies of the data pointssorted according to their position along a space fillingcurve, such as the Peano curve, in a way that allows usto make performance guarantees and without assumingthat the dimensionality d is constant. The first...