Managing Spatiotemporal Data:MV3R-tree

MV3R-tree

The MV3R-tree was proposed by Yufei and Papadias in [19] and is demonstrated to process time-stamp and interval queries efficiently. Timestamp queries discover all objects that intersect a window query at a particular timestamp. On the other hand, interval queries include multiple timestamps in the discovered response. While the spatial data structures proposed before have been demonstrated [9,19] to be suitable for either of these queries (or a subset of it), none of them have been established to process both timestamp and interval queries efficiently. MV3R-tree has addressed limitations in terms of efficiency of the above trees in handling both of these queries. MV3R-tree consists of a multi-version R-tree (MVR- tree) and an auxiliary 3D R-tree built on the leaves of the MVR-tree. Although the primary motivation behind the development of MV3R-tree are Multiversion B-trees [20] (which are extended from B+ trees), they are significantly different from these versions. Before we proceed further, let us understand the working of a multiversion B-tree.

A typical entry of a multiversion B-tree takes the following form < id, timestart, timeend, P >. For non-leaf nodes, timestart and timeend are the minimum and maximum values respectively in this node and P is a pointer to the next level node. For a leaf node, the time-stamps timestart and timeend indicate when the object was insert and deleted from the index and pointer P points to the actual record with a corresponding id value. At time timecurrent, the entry is said to be alive if timestart < timecurrent, otherwise dead [19]. There can be multiple roots in a Multiversion B-tree, where each root has a distinguishing time-range it represents. A search on the tree begins at identifying the root within which the time-stamp of the query belongs. The search is continued based on the id, timestart and timeend. A weak version condition specifies that for each node, except the root, at least K.T entries are alive at time t, where K is the node capacity and T is the tree parameter.

This condition ensures that entries alive at the identical time-stamps are in a majority of the cases assembled together to allow easy time stamp queries.

3D R-tree are very space-efficient and can handle long interval queries efficiently. However, timestamp and short-interval queries using 3D R-trees are expensive. In addition to this, 3D R-trees do not include a methodology such as the weak version condition to ensure that each node has a minimum number of live entries at a given timestamp. HR-trees [18], on the other hand, maintain an R-tree (or its derivative) for each timestamp and the timestamp query is directed to the corresponding R-tree to be searched within it. In other words, the query disintegrates into an ordinary window query and is handled very efficiently. However, in case of an interval query, several timestamps should search the corresponding trees of all the timestamps constituting the interval. The original work in HR-tree did not present a schema for handling interval queries; however, authors in [19] have proposed a solution to this problem by the use of negative and positive pointers. The performance of this schema is then compared with MV3R-tree in [19]. It is demonstrated that MV3R-trees outperform HR-trees and 3D R-trees even in extreme cases of only timestamp and interval-based queries.

Multiversion 3D R-trees (MV3R-trees) combine a multiversion R-tree (MVR-tree) and a small auxiliary 3D R-tree built on the leaf nodes of the MVR-tree as shown in Figure 22.12. MVR-trees maintain multiple R-trees and has entries of the form < M BR,

timestart, timeend, P >, where MBR refers to Minimum bounding rectangle and other en- tries are similar to B+ trees. An example of a 3-D visualization of a MVR-tree of height 2 is shown in Figure 22.13. The tree consists of Object cubes (A-G), leaf nodes (H-J) and root of the tree K.Detailed algorithms for insertion and deletion in these trees are provided in [19]. Time-stamp queries can be answered efficiently using MVR-trees. An auxiliary 3D R-tree is built on the leaves of the MVR-tree in order to process interval queries. It is suggested that for a moderate node capacity, the number of leaf nodes in an MVR-tree is much lower than the actual number of objects, hence this tree is expected to be small compared to a complete 3D R-tree.

Performance analysis has shown that the MV3R-tree offers better tradeoff between query performance and structure size than the HR-tree and 3D R-tree. For typical situations where workloads contain both timestamp and interval queries, MV3R-trees outperform HR- trees and 3D R-trees significantly. The incorporation of the auxiliary 3D R-tree not only accelerates interval queries, but also provides flexibilities towards other query processing, such as, spatiotemporal joins.