SQR-tree: A spatial index using semi-quantized MBR compression scheme in R-tree

The increase in spatial data for location-based service (LBS) in mobile computing or geographic information system (GIS) has led to more research on spatial indexing, such as R-tree. Nevertheless, few studies have attempted to improve performance by reducing the size of the index. If the minimal bounding rectangles (MBRs) that represent objects in R-tree are compressed, the index size is reduced and location-based services are provided to the user more rapidly. This study proposes a new MBR compression scheme using MBR semi-quantization (SqMBR) scheme and SQR-tree, which indexes spatial data using R-tree. Since the SqMBR scheme decreases the size of MBR keys, halves the enlargement of a quantized MBR (QMBR), and increases node utilization, it improves the overall search performance. This scheme decreases quantized space more than existing quantization schemes. The SqMBR scheme increases the utilization of disk allocation units. In spatial index, a greater number of node entries lowers tree heights and decreases the number of node accesses, thereby shrinking disk input/output. This study analyzes the number of node accesses mathematically and evaluates the performance of SQR-tree using real location data. The results show that the proposed index performs better than existing MBR compression schemes.