Quicker range- and k-NN joins in metric spaces

We consider the join operation in metric spaces. Given two sets A and B of objects drawn from some universe U, we want to compute the set A x B = {(a, b) is an element of A (sic) B vertical bar d(a, b) <= r) efficiently, where d: U x U -> R+ is a metric distance function and r is an element of R+ is user supplied query radius. In particular we are interested in the case where we have no index available (nor we can afford to build it) for either A or B. In this paper we improve the Quickjoin algorithm [6], inspired by the well-known Quicksort algorithm, by (i) replacing the low level component that handles small subsets with essentially brute-force nested loop with a more efficient method; (ii) showing that, contrary to Quicksort, in Quickjoin unbalanced partitioning can improve the algorithm; (iii) making the algorithm probabilistic while still obtaining most of the relevant results; and (iv) improving the (worst case) work space needed, from O(n(2)) to O(logn), where n is the size of the dataset(s). We also discuss pivot selection, show how to adapt Quickjoin to compute k-nearest neighbor joins and sketch a parallel version of the algorithm. The experimental results show that the method works well in practice. (C) 2014 Elsevier Ltd. All rights reserved.