Quicker range- and k-NN joins in metric spaces. (August 2015)

• Record Type: Journal Article
• Authors: Fredriksson, Kimmo; Braithwaite, Billy
• Is Part Of: Information systems. Volume 52(2015)
• Page Start: 189
• Page End: 204
• Publication Date: 2015-08
• Subjects: Metric spaces -- Similarity joins -- k-nearest neighbors -- Range searching; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2014.09.006
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: 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 ⋈ B = { ( a, b ) ∈ A × B | d ( a, b ) ≤ r } efficiently, where d : U × U → R + is a metric distance function and r ∈ 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 ( log n ), 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. Abstract : Highlights: We substantially improve the space and time complexity of the Quickjoin algorithm. We show how to select good pivots for Quickjoin. We generalize the Quickjoin algorithm to handle k -nearest neighbor joins.