Managing Spatio-Temporal Data:Overlapping Linear Quad tree.
Overlapping Linear Quad tree
Tzouramanis, Vassilakopoulos and Manolopoulos in [4] proposed Multi version linear quad trees (MVLQ), also called overlapping linear quad trees, which are analogous to Multi version B- trees (MVBT) [5], but with significant differences. Instead of storing transaction time for each individual object in MVBT, an MVLQ consolidates object descriptors that share a same transaction time. As it will be evident from the following discussion, these object descriptors are code words derived from a linear representation of multiversion quadtrees.
The idea of storing temporal information about the objects is based upon including a parameter for transaction time for these objects. Each object is given a unique time-stamp Ti (transaction time), where i ∈ [1..n] and n is the number of objects in the database.
This time stamp implicitly associates a time value to each record representing the object. Initially, when the object is created in the database, this time-interval is set equal to [Ti, ∗).
Here, ‘*’ refers to as-of-now, a usage indicating that the current object is valid until a unspecified time in the future, when it would be terminated (at that time, * will be replaced by the Tj , j ∈ [1..n] and j > i, the time-stamp at the time when the object is terminated).
Before we proceed further, let us gather some brief background in regional Quadtrees, commonly called quadtrees, a spatial data structure. In the following discussion it is assumed that a Spatiotemporal data structure (STDS) is required to be developed for a sequence of evolving regional images, which are stored in an image database. Each image is assumed to be represented as a 2N × 2N matrix of pixel values, where N is a positive integer.
Quadtree is a modification of T-pyramid. Every node of the tree, except the leaves, has four children (NW: north-western, NE: north-eastern, SW: south-western, SE: south- eastern). The image is divided into four equal quadrants at each hierarchical level, but it is not necessary to store nodes at all levels. If a parent node has four children of the same homogeneous (for example, intensity) value, it is not necessary to record them. Figure 22.1 represents an image and its corresponding quad tree representation. Quad tree is a memory- resident data structure, with each node being stored as a record pointing to its children. However, when the represented object becomes too large it may not be possible to store
Several linear representations of regional quad trees have been proposed, but fixed length (FL), fixed length-depth (FD) and variable length (VL) versions have attracted most attention. We refer the interested reader to [6] for details on these representations, while we concentrate on the FD representation. In this representation, each homogeneous node is represented by a pair of two codes, location code and level number . Location node C denotes the correct path to this node when traversing the Quad tree from its root till the appropriate leaf is reached and a level number L refers to the level at which the node is located. This makes up the fixed length-depth linear implementation of Quad tree.The quadrants NW, NE, SW and SE are represented as 0, 1, 2 and 3 respectively. The location codes for the homogeneous nodes of a quad tree are presented in Figure 22.1.
A persistent data structure (Chapter 31) [7] is one in which a change to the structure can be made without eliminating the old version, so that all versions of the structure persist and can at least be accessed (the structure is said to be partially persistent) or even modified (the structure is said to be fully persistent). Multi-Version Linear Quad-tree (MVLQ) is an example of a persistent data structure, in contrast to Linear Quad tree, a transient data structure. In MVLQ each object in the database is labeled with a time for maintaining the past states. MVLQ couples time intervals with spatial objects in each node.
The leaf of the MVLQ contains the data records of the format:
where,
- C is the location code of the homogeneous node of the region Quadtree,
- L is the level of the region quad tree at which the homogeneous node is present,
- T represents the time interval when the homogeneous node appears in the image sequence,
- EndTime is Transaction time when the homogeneous leaf node becomes historical. The non-leaf nodes contain entries of the form [4]:
where,
- CI is the smallest C recorded in that descendant node,
- P I is the time interval that expresses the lifespan of the latter node,
- Ptr is a pointer to a descendant node,
- Start Time is the time instant when the node was created.
The MLVQ structure after the insertion of image given in Figure 22.1.a is given in Figure 22.2.
In addition to the main memory structure of the MVLQ described above, it also contains two additional main memory sub-structures: Root*table and Depth First expression (DF- expression) of the last inserted object.
Root*table: MVLQ has one tree for each version of the data. Consequently, each version can be reached through its root which can be identified by the time-interval of the version that it represents and a pointer to its location. If T II is the time interval of the root, given by T II=[Ti, Tj ), where i, j ∈ [1..n], i<j, and P trI is a pointer to the physical address of the root, then each record in the Root*table identifying a root is represented in the following form:
DF -expression of the last inserted object [4,8]: The purpose of Depth first expression (DF- expression) is to contain the pre-fetched location of the homogeneous nodes of last insert data object. The advantage of this storage is that when a new data object is being inserted, the stored information can be used to calculate the cost of deletions, insertions and/or updates. If the DF-expression is not stored, then there is an input/output cost associated with locating the last insert object’s homogeneous nodes locations. The DF-expression is an array representation of preorder traversal of the last inserted object’s Quadtree.
Insertion of an Object in MVLQ
The first step in insertion of a quad code of a new object involves identifying the corresponding leaf node. If the corresponding leaf node is full, then a node overflow [4] occurs. Two possibilities may arise at this stage, and depending on the Start Time field of the leaf, a split may be initiated. If NC is the node capacity, k and c are integer constants (greater than zero), then the insertion is performed based on the algorithm presented in Figure 22.3.
Deletion of an Object in MVLQ
The algorithm for the deletion of an object from MVLQ is straightforward. If Ti = Start Time, then physical deletion occurs and the appropriate entry of the object is deleted from the leaf. If number of entries in the leaf < INC/kl (threshold), then a node-underflow is handled as in B+ tree with an additional step of checking for a sibling’s Start Time for key redistribution. IfTi > Start Time, then logical deletion occurs and the temporal information
of an entry between range ([Ti, ∗), [Ti, Tj )) is updated. If an entry is logically deleted in a leaf with exactly INC/kl present quadcode versions, then a version underflow [5] occurs that causes a version split of the node, copying the present versions of its quadcodes into a new node. After version split, the number of present versions of quadcodes is below (1+e) INC/kl and a merge is then attempted with a sibling or a copy of that sibling.
Updating an Object in MVLQ
Updating a leaf entry refers to update of the field L(level) of the object’s code. This is implemented in a two-step fashion. First, a logical deletion of the entry is performed. Second, the new version is inserted in place of that entry through the steps outlined above.
Comments
Post a Comment