17 Multimedia Data Structures
Dr R. Baskaran
MULTIMEDIA DATA STRUCTURES
It is observed that one of the data sources being consulted there is a geographic information source. Geographic data comes in many flavors. In its simplest form, a geographic information system (GIS) stores information about some physical region of the world. This stored information could be just a map (image) containing some salient features. In this case, the map is viewed as a two-dimensional image, and certain points on the map are considered to be of interest. These points are then stored in one of many specialized data structures.
The k-d tree is used to store k-dimensional point data. It is not used to store region data. Thus, a 2-d tree (i.e., k — 2) stores two-dimensional point data, a 3-d tree stores three-dimensional point data, and so on. We will deal with 2-d point data, and we will later indicate how this approach may be generalized to 3-d data.
In particular, the INFO field of a node in a k-d tree can be any user-defined type whatsoever. The exact content of this field depends upon the application that the user has in mind. For example, the INFO field could be just a string field, depicting the name of a place, or it could be a record containing fields name: string and population: integer, or something else altogether. The fields XVAL and YVAL denote the coordinates of a point associated with the node. The LLINK and RLINK fields point to two children.
Suppose T is a pointer to the root of a 2-d tree. If N is a node in this tree, then the level of node N is defined inductively as:
A 2-d tree is any binary tree satisfying the following conditions:
1. If N is a node in the tree such that level (N) is even, then every node M in the subtree rooted at N.LLINK has the property that M.XVAL < N.XVAL, and every node P in the subtree rooted at N.RLINK has the property that P.XVAL > N.XVAL.
2. If N is a node in the tree such that level(N) is odd, then every node M in the subtree rooted at N.LLINK has the property that M.YVAL < N.YVAL, and every node P in the subtree rooted at N.RLINK has the property that P.YVAL > N.YVAL.
INSERT AND SEARCH IN 2-D TREES:
An algorithm for insertion into a 2-d tree may easily be defined. Inserting a node N into the tree pointed to by T may be informally accomplished as follows. Check to see if N and T agree on their XVAL and YVAL fields. If so, just overwrite node T, and we are done. Otherwise, branch left if N.XVAL < T.XVAL, and branch right otherwise. Suppose P denotes the child we are examining. If N and P agree on their XVAL and YVAL fields, just overwrite node P, and we are done; else branch left if N.YVAL < P.YVAL, and branch right otherwise. Repeat this procedure, branching on XVALs when we are at even levels in the tree, and on YVALs when we are at odd levels in the tree. This algorithm is easily formalized.
The basic outline of our deletion algorithm, as applied to interior nodes N, consists of three steps:
Step 1: Find a candidate replacement node R that occurs in T; for i € {l, r}.
Step 2: Replace all of N’s non link fields by those of R.
Step 3: Recursively delete R from Ti.
The above recursion is guaranteed to terminate because T; for i € {£, r} has strictly smaller height than the original tree T from which we are deleting the node.The critical step in the above algorithm is to find a suitable “candidate replacement node.” The desired replacement node R must bear the same spatial relation to all nodes P in both Tg and Tr that N bore to P; that is, if P is to the southwest of N, then P must be to the southwest of R, if P is to the northwest of N, then P must be to the northwest of R, and so on. This means that the desired replacement node R must satisfy the following properties:
1. Every node M in T£ is such that M.XVAL < i?.XVAL if level(N) is even, and M.YVAL < R.YVAL if level(N) is odd.
2. Every node M in Tr is such that M.XVAL > i?.XVAL if level(N) is even, and M.YVAL > .R.YVAL if level(N) is odd.
If Tr is not empty, and level(N) is even, then any node in Tr that has the smallest possible XVAL field in Tr is a candidate replacement node.
In general, finding a replacement node from the left subtree is possible only under some conditions. If level{N) is even, an appropriate replacement node in T € is any node whose XVAL field is the largest possible XVAL value in Tf. Similarly, if level{N) is odd, then we may use any node in Tg that has that maximal possible YVAL field as a replacement node. The problem with this approach is that there may be more than one node in Tt that has such a maximal XVAL (or YVAL) field, and in this case, the second condition in the definition of 2-d trees would be violated by the three-step procedure outlined above. Thus, in general, if AT is an interior node, and we wish to delete AT from T, we prefer to find a replacement from the right subtree, since finding a candidate replacement from the left subtree may be infeasible.
This raises the question of what to do if node N has an empty right subtree (i.e., AT.RLINK = NIL). In this case, we can choose as a replacement node, a node R from Tt that has the smallest rvalue in Tt (if level(N) is even) or the smallest j-value in Tt (if level(N) is odd). We then modify the three-step algorithm above a little bit by slightly changing its second step:Step 2 (modified): Replace all of N’s non-link fields by those of R. Set N.RLINK = N.LLINK, and set N.LLINK = NIL.
POINT QUADTREES:
The point quadtree, like the 2-d tree, is used to represent point data in two-dimensional spaces. Unlike the 2-d tree, point quadtrees always split regions into four parts. In a 2-d tree, node N splits a region into two by drawing one line through the point (N\XVAL,N\YVAL). This line may be either horizontal (if level(N) is odd) or vertical (if level(N) is even). In the case of a point quadtree, node N splits the region it represents by drawing both a horizontal and a vertical line through the point (N.XVAL,N.YVAL). These four parts are called the NW (northwest), SW (southwest), NE (northeast), and SE (southeast) quadrants determined by node N, and each of these quadrants corresponds to a child of node N. Thus, quadtree nodes may have up to four children each. Before proceeding any further, we provide a simple definition of the node structure of a point quadtree node:
qtnodetype = record
INFO: infotype;
XVAL: real;
YVAL: real;
NW,SW,NE,SE: tqtnodetype
End
DELETION IN POINT QUADTREES:
When deleting a node N from a point quadtree having root T, we need to try, as we did in the case of deletion in 2-d trees, to find an appropriate replacement node for non leaf nodes. In the case of leaf nodes, of course, deletion is completely trivial: we just set the appropriate link field of node N’s parent to NIL and return the node to available storage.
Deletion in point quadtrees is very complex may be used to illustrate why. First and foremost, each node in a point quadtree represents a region, and this region is defined somewhat differently than in the case of a 2-d tree. As in the case of 2-d trees, however, it suffices to associate four constraints of the form x > C\, x < C2, y > C3, and y < C4 for constants Ci,…, C4. Thus, as in the case of 2-d trees, where we expanded nodetype to newnodetype, we may expand the node structure qtnodetype to a new node structure newqtnodetype having the same types of fields (XLB, YLB, XUB, YUB) that we had seen earlier.
newqtnodetype = record
INFO: infotype;
XVAL.YVAL: real;
XLB,YLB,XUB,YUB: real u{-∞,+∞};
NW,SW,NE,SE: fiewqtnodetype
End
