Building Search Structures on the GPU

The affordable parallel computing capability provided by the general-purpose graphics processing unit (GPGPU) becomes accessible on most popular computing platforms. Many applications can benefit from redesign for these heterogeneous systems by moving some computation to the GPU. Although the introduction of CUDA and OpenCL makes modern GPU programming much easier than hacking shaders, it is still not trivial to develop GPU programs that fully exploit the capability of the hardware. To further ease software development for the GPU, a lot of well-optimized high-performance parallel primitives that solve common problems have been released. With these reliable building blocks, developers can focus on their custom components and thus become more productive. In this dissertation, we continue this effort and build search structures on the GPU.;For the low-dimensional k-approximate nearest neighbors search problem, we implement the shifted sorting algorithm. In each iteration, the data and query points are shifted with a certain amount and then sorted together in Morton code order. Different shift amounts lead to different relative orders among the points; the nearest neighbors of a query in the original space are very likely to have similar Morton codes with the query in some of the sorted lists. We consider a query's 1D nearest neighbors from all the sorted lists as the candidates and select the best k of them as the result. Our approach is independent of the distributions of the data and query points and performs more quickly than the state-of-the-art methods on difficult problem instances.;To solve the high-dimensional k-nearest neighbors search problem, we introduce a robust efficient brute-force implementation. A highly optimized matrix multiplication subroutine is modified to calculate the squared Euclidean distances between queries and references. The nearest neighbors selection is accomplished by a parallel truncated merge sort based on the Merge Path algorithm, which partitions merging two sorted lists into several independent small mergings. Compared to other published works, our program is faster and it handles larger inputs.;Traditional GPU data structures do not support update operations and have to be rebuilt if the data changes. As the initial attempts to build dynamic data structures on the GPU, we propose two dynamic sorted structures: the GPU search array and the GPU search tree. Both of them support batch insertion, with which we can incrementally build the structures. After an insertion, the structures resume searchability and serve both item queries and range queries using binary search. We describe various implementation strategies for the three operations and illustrate their performance comparisons.