Parallel randomized KD-tree forest on GPU cluster for image descriptor matching

Many high dimensional data mining applications involve the nearest neighbor search (NNS) on a KD-tree. Randomized KD-tree forest enables fast medium and large scale NNS among high dimensional data points. In this paper, we present massively parallel algorithms for the construction of KD-tree forest, and NNS on a cluster equipped with massively parallel architecture (MPA) devices of graphical processing unit (GPU). This design can accelerate the KD-tree forest construction and NNS significantly for the signature of histograms of orientations (SHOT) 3D local descriptors by factors of up to 5.27 and 20.44, respectively. Our implementations will potentially benefit realtime high dimensional descriptors matching