An Efficient Parallel Algorithm for High Dimensional Si
Khaled A. Alsabti, Sanjay Ranka, Vineet Kumar Singh · 1998
Multidimensional similarity join finds pairs of multi- dimensional points that are within some small distance of each other: The 6-k-d-B tree has been proposed as a data structure that scales better as the number of dimensions in- creases compared to previous data structures. We present a cost model of the E-k-d-B tree and use it to optimize the leaf size. We present novel parallel algorithms for the similar- ity join using the E-k-d-B tree. A load-balancing strategy based on equi-depth histograms is shown to work well for uniform or low-skew situations, whereas another based on weighted equi-depth histograms works far better for high- skew datasets. The latter strategy is only slightly slower than the former strategy for low skew datasets. Furthel; its cost is proportional to the overall cost of the similarity join. The E-k-d-B tree is a new multidimensional index struc- ture that has been proposed for performing similarity join on high-dimensional points (2). It has been shown to be considerably superior to other structures for performing the similarity join on high-dimensional points. In this paper, we present a cost model for performing similarity join using the 6-k-d-B tree. We use our cost model to dynamically determine the leaf size threshold. This threshold has a significant effect on the cost of the sim- ilarity join operation. Our experimental results show that our model is reasonably effective. This cost model is also useful for its parallelization. The parallelization of similarity join is difficult because of skewed amounts of work required in different parts of the tree. The amount of work required for different parts of the tree can be a superlinear function of the number of as- sociated points. In this paper, we present a novel sampling- based scheme for the parallelization of this problem. Our scheme uses a subset of data to estimate the amounts of work required based on the cost model discussed earlier. A comparison with a simplistic scheme based on assigning approximately equal numbers of points to different numbers of processors shows that our scheme performs significantly better in the presence of data skews, even for 16 processors. The rest of this paper is organized as follows. In Section 2, we describe how to determine the optimal or near opti- mal leaf size of the c-k-d-B tree. In Section 3, we describe several parallel algorithms for computing the similarity join and a novel load-balancing strategy suitable for paralleliz- ing problems which are sensitive to the presence of data skew and are not iterative in nature. Section 4 presents ex- perimental results. Section 5 presents our conclusions.