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

Jongwan Kim, SeokJin Im, Sang Won Kang, Chong Sun Hwang, Sang-Geun Lee

    Research output: Contribution to journalArticlepeer-review

    5 Citations (Scopus)

    Abstract

    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.

    Original languageEnglish
    Pages (from-to)1541-1563
    Number of pages23
    JournalJournal of Information Science and Engineering
    Volume23
    Issue number5
    Publication statusPublished - 2007 Sept

    Keywords

    • Index compression
    • Index packing
    • Location-based services
    • Minimum bounding rectangle
    • Quantization
    • R-tree
    • Spatial index

    ASJC Scopus subject areas

    • Software
    • Human-Computer Interaction
    • Hardware and Architecture
    • Library and Information Sciences
    • Computational Theory and Mathematics

    Fingerprint

    Dive into the research topics of 'SQR-tree: A spatial index using semi-quantized MBR compression scheme in R-tree'. Together they form a unique fingerprint.

    Cite this