An efficient balanced hierarchical data structure for multiversion accesses to spatio-temporal data

In the management of spatio-temporal data, a data structure must manage multiple versions of a data structure efficiently, and provide quick and flexible search methods not only for temporal or spatial queries, but also for the combined queries of spatial and temporal intervals. The persistent MD-tree, called the PMD-tree is developed by extending a hierarchical data structure to support accesses to multiple versions. The PMD-tree has the novel properties that the tree representing any time aspect of a data structure is always balanced, and that the storage utilization rate is more than 66.6%. The algorithms of the PMD-tree, space and time analyses, and search performances compared to the MD-tree are described in the paper.