Approximate -Closest-Pairs with Space Filling Curves

An approximate algorithm to efficiently solve the k-Closest-Pairs problem in high-dimensional spaces is presented. The method is based on dimensionality reduction of the space through the Hilbert space filling curve and performs at most scans of the data set. After each scan, those points whose contribution to the solution has already been analyzed, are eliminated from the data set. The pruning is lossless, in fact the remaining points along with the approximate solution found can be used for the computation of the exact solution. Although we are able to guarantee an approximation to the solution, where denotes the used Lt metric, experimental results give the exact -Closest-Pairs for all the data sets considered and show that the pruning of the search space is effective.