Top-k Closest Pairs Join Query: An Approximate Algorithm for Large High Dimensional Data

In this paper we present a novel approximate algorithm to calculate the top $k$ closest pairs join query of two large and high dimensional data sets. The algorithm has worst case time complexity ${\cal O}(d^2nk)$ and space complexity ${\cal O}(nd)$ and guarantees a solution within a ${\cal O}(d^{1+\frac{1}{t}})$ factor of the exact one, where $t\in\{1,2,\ldots,\infty\}$ denotes the Minkowski metrics $L_t$ of interest and $d$ the dimensionality. It makes use of the concept of space filling curve to establish an order between the points of the space and performs at most $d+1$ sorts and scans of the two data sets. During a scan, each point from one data set is compared with its closest points, according to the space filling curve order, in the other data set and points whose contribution to the solution has already been analyzed are detected and eliminated. Experimental results on real and synthetic data sets show that our algorithm (i) behaves as an exact algorithm in low dimensional spaces; (ii) it is able to prune the entire (or a considerable fraction of the) data set even for high dimensions if certain separation conditions are satisfied; (iii) in any case it returns a solution within a small error to the exact one.