| dc.description.abstract | This thesis investigates the performance of memory resident spatial search, focusing on the R-tree. The characteristics of modern computer architectures are first visited to understand how they have changed since the invention of the R-tree, and what difference moving the database from disk to memory can be expected to make. The design of four well known R-trees are introduced, implemented and used to reproduce the results of Beckmann and Seeger.
Next, four optimizations for the R-tree search are suggested in an attempt to speed up search by improving the memory layout, through explicit parallelization using SIMD instruction, and by applying pruning at a lower level than classical search in R-tree does. The results show that the optimizations often have the intended effects and yield speedups in excess of 1.3 for all tested data sets, and almost reach 1.8 in specific cases.
More importantly, it is found during the analysis that there exists a tradeoff between sequential memory access, with an associated computational cost, and random memory access arising due to the tree structure. Improving one aspect alone may offsets this balance and improve performance, but the true challenge is to create the combined approach needed to fully exploit modern computer architectures during search in memory resident R-trees. | |
