Enhancing R tree spatial indexing using adaptive particle swarm optimization algorithm

Full abstract

Read the full abstract

With the rapid growth of spatial information, efficient geospatial data management and fast query processing have become critical challenges in large-scale spatial databases. The R-tree is a widely used spatial indexing structure due to its efficiency in indexing multidimensional data and supporting range and nearest-neighbor queries. However, this also causes serious limitations, such as excessive overlap of minimum bounding rectangles (MBRs), slowing down the query processing. In addition, frequent insertions and deletions result in an unbalanced R-tree with a poor data distribution. Poor node-splitting and merging strategies further worsen storage utilization and increase management overhead. This paper proposes PSO-RT, a new methodology that combines the PSO algorithm with the R-tree to overcome these limitations. The main research question to be answered in the paper is the following: Integrating PSO into the R-tree structure effectively reduces MBR overlap, balances the tree, and improves storage efficiency for faster query processing? The research approach is to adopt an experimental design where PSO is applied to dynamically optimize node splits and node merges in the R-tree. The PSO algorithm evaluates the solutions using a fitness function that combines the reduction of MBR overlap with the minimization of tree height. Three different datasets were experimented with to study the efficiency of PSO-RT: Synthetic, OpenStreetMap, and TIGER. These results strongly evidence that PSO-RT greatly enhances spatial indexing performance. The response time to the query improved to 35.7%, with MBR overlap reduced by 42.7%, and improvement in node utilization up to 19.6%. In contrast, the baseline R-trees have shown overhead from 67.9% to 75.8% on insertion and deletion times, respectively. These results confirm that PSO-RT is flexible and scalable on different datasets, making it a feasible solution for efficient geospatial data management. It is recommended that future research be focused on hybrid optimization techniques to reduce overhead costs while maintaining or increasing query performance. The study recommends using PSO-RT in high-performance spatial indexing applications and handling large volumes of data.