Performance Evaluation of Main-Memory R-tree Variants

摘要: There have been several techniques proposed for improving the performance of main-memory spatial indexes, but there has not a comparative study their performance. In this paper we compare six R-tree variants: R-tree, R*-tree, Hilbert CR-tree, CR*-tree, and CR-tree. CR*-trees CR-trees are respectively natural extension R*-trees R-trees by incorporating CR-trees’ quantized relative minimum bounding rectangle (QRMBR) technique. Additionally, apply optimistic, latch-free index traversal (OLFIT) concurrency control mechanism B-trees to variants while using GiST-link We perform extensive experiments in two categories sequential accesses concurrent accesses, pick following best trees. search, update, mixture them. search if data is uniformly distributed, skewed, also provide detailed observations experimental results, rationalize them based on characteristics individual As far as know, our work first comprehensive variants. The results useful guideline selecting most suitable structure various cases.