Numerous spatial indexing techniques have studied until now. However, most of these have been devised to process only spatial selections such as queries and window queries efficiently. The spatial join is an operation which frequently occurrs in spatial database systems and incurrs high query processing costs. Therefore, an indexing technique is needed to process spatial join efficiently.
This thesis describes an indexing technique, which improves the join performance without much effecting the performance of spatial selections, and a sublinear time join algorithm using the indexing technique. We call this indexing technique an LR-H tree (Linear Region tree on Hilbert ordering) or simply an LR tree. The main idea of the LR tree is an one-dimensional ordered index facilitates the worst case computatiuon of overlaps between trees in linear time and makes the merge join possible, and MBR fields in internal nodes preserve the spatial proximity well like an R tree family. The tree matching(TM) join is the most popular join method in index structures which have MBR fields like R tree. Therefore, we propose a new sublinear time join algorithm which mixes the merge join and the TM join.
We have compared the performance of the LR tree proposed in this thesis with the R tree and $R^*$ tree through simulations. According to our simulation results, the LR tree outperforms the R tree and $R^*$ tree in spatial joints, and shows better or similar performance compared with the R tree and the $R^*$ tree in spatial selections.
