Novel method for faster construction of R-Tree spatial index using text-based spatial attributes

Abstract

Spatial indexing is a key component of both traditional and big spatial data processing systems because unlike the traditional partitioning methods, they use spatial attributes of objects as a basis for partitioning the data. R-Tree based spatial indexing is one the most used methods of partitioning spatial data. R-Tree is a multi-level tree that uses tuples of identifiers and geographic bounding rectangles as nodes.

Spatial keywords or text-based spatial attributes stored in a spatial data set, allow the use of WFS-G web "Gazetteer" service to overcome some of the shortcomings of spatial indexing, when processing polygons that consists of a very large number of vertices. The new proposed algorithm reduces the time for building minimum bounding rectangles MBRs which is a main factor in creating spatial indexes and spatial partitioning, by using the spatial keywords to obtain minimum bounding rectangles via web "Gazetteer" service. The obtained results prove the capability of the algorithm in reducing R-Tree construction time when the number of vertices of polygons of the data set is above a flexible decision threshold calculated during the initialization phase of the algorithm.