University of Houston

R-trees are data-partitioning multidimensional index structures that partition the data to bounded rectangles; neighboring objects are grouped in the same tree node thus speeding up nearest neighbor search (k-NN search). This thesis implements the quadratic R-tree, the packed R-tree and preprocessing bulk loading algorithms, such as the space filling curve ordering (Hilbert ordering) and the spectral locality preserving mapping (Spectral LPM), as well as different types of approximate R-tree k-NN search algorithms, namely, the ε-approximation and the probabilistic approximation. Furthermore, precomputation methods and parallel computing (OpenMP) techniques are investigated to reduce the time for repetitive k-NN search. Experiments using large spatial datasets will be presented for comparing and evaluating the above algorithms.

Our results show that the performance of the approximate k-NN search methods heavily depends on R-tree structures and datasets used. R-trees constructed by preprocessing bulk loading algorithms speed up the k-NN search significantly and in general, Hilbert ordering outperforms Spectral LPM. In addition, OpenMP parallelism is suitable for repetitive R-tree k-NN search.