Parallel indexing technique for spatio-temporal data

The requirements for efficient access and management of massive multi-dimensional spatio-temporal data in geographical information system and its applications are well recognized and researched. The most popular spatio-temporal access method is the R-Tree and its variants. However, it is difficult to use them for parallel access to multi-dimensional spatio-temporal data because R-Trees, and variants thereof, are in hierarchical structures which have severe overlapping problems in high dimensional space. We extended a two-dimensional interval space representation of intervals to a multi-dimensional parallel space, and present a set of formulae to transform spatio-temporal queries into parallel interval set operations. This transformation reduces problems of multi-dimensional object relationships to simpler two-dimensional spatial intersection problems. Experimental results show that the new parallel approach presented in this paper has superior range query performance than R*-trees for handling multi-dimensional spatio-temporal data and multi-dimensional interval data. When the number of CPU cores is larger than that of the space dimensions, the insertion performance of this new approach is also superior to R*-trees. The proposed approach provides a potential parallel indexing solution for fast data retrieval of massive four-dimensional or higher dimensional spatio-temporal data.