Managing Spatiotemporal Data:HR-tree

HR-tree

One possible way to index spatiotemporal data is to build one R-tree for each timestamp, which is certainly space-inefficient. The demerit of 2+3 R-tree is that it requires two stores to be searched to answer a query. The HR-tree [18] or Historical R-tree “compresses” multiple R-trees, so that R-tree nodes which are common in two timestamps are shared by the corresponding R-trees. The main idea is based on the expectation that a vast majority of indexed points do not change their positions at every time stamp. In other words, it is reasonable to expect that a vast majority of spatial points will ‘share’ common nodes in respective R-trees. The HR-tree exploits this property by keeping a ‘logical’ linkage to a previously present spatial point if it is referenced again in the new R-tree. Consider two R-trees in Figure 22.9 and Figure 22.10 at two different time stamps (T0, T1). An HR-tree for these R-trees is given in Figure 22.11.

clip_image002

FIGURE 22.11: The HR-tree.

Comments

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

Drawing Trees:HV-Layout