18 Multimedia Data Structures

Dr R. Baskaran

The MX-Quadtree

 

In the case of both 2-d trees and point quadtrees, the “shape” of the tree depends upon the order in which objects are inserted into the tree. In particular, the order affects the height of the tree, which, in turn, may affect the complexity of search and insertion operations. Also, for both 2-d trees and point quadtrees, each node N represents a region and splits the region into two (for 2-d trees) or four (for point quadtrees) subregions. The split may be uneven, depending upon exactly where the point (iV.XVAL,iV.YVAL) is located inside the region represented by node N. In contrast, the aim behind MX-quadtrees was to ensure that the shape (and height) of the tree was independent of the number of nodes present in the tree, as well as the order of insertion of these nodes. Additionally, the MX-quadtree aimed at providing efficient deletion and search algorithms.

 

In short, the MX-quadtree works as follows: First, we assume that the map being represented is split up into a grid of size (2* X 2k) for some k. The application developer is free to choose k to reflect the desired granularity, but once k is chosen, it must be kept fixed.

  • Node Structure: Exactly the same as for point quadtrees, except that the root of an MX-quadtree represents the region speficied by XLB= 0, XUB= 2k, YLB= 0, YUB=2k.
  • When a region gets “split”, it gets split down the middle.
  • Thus, if N is a node, then the regions represented by the four children of N

 

INSERTION INTO MX-QUAD TREES:

 

Let us now examine how we might insert points into an MX-quadtree. Each point (x,y) in an MX-quadtree represents the lxl region whose lower-left corner is (x,y). A point is inserted at the node representing the lxl region corresponding to that point. Suppose now that we wish to insert the points A, B, C, and D shown in Figure. We proceed as follows:

 

The insertion of point A with coordinates (1,3) causes the following: The root node represents the entire region, and A lies in its NW quadrant. Thus, the root’s NW child corresponds to the 2×2 region whose lower-left corner is the point (0, 2). The point A is in the NE subquadrant of this region. Figure shows the MX-quadtree resulting after the insertion of A; Figure shows the split of the regions involved. Note that point A is inserted at level 2 in the tree, and this level is identical to k. In general, points will always be inserted at level k in the MX-quadtree.

 

The insertion of point B with coordinates (3,3) causes a branch to the NE quadrant as B. Thus, the root’s NE child corresponds to the 2×2 region whose lower-left corner is the point (2, 2). The point B is in the NE sub- quadrant of this region. Figure given below show the resulting situation.

 

The insertion of point C with coordinates (3,1) proceeds as follows: C is in the SE quadrant of the whole region. This causes us to create a new node.

 

                     After insertion of D

     DELETION IN MX-QUAD TREES:

  • Deletion in an MX-quadtree is a fairly simple operation, because all points are represented at the leaf level.
  • If N is an interior (i.e. non-leaf) node in an MX-quadtree whose root is pointed to by T, then the region implicitly represented by node N contains at least one point that is explicitly contained in the tree.
  • If we wish to delete a point (x, y) from tree T, we try to preserve this property.

 

This can be done as follows.

  • First, we set the appropriate link of N’s parent to NIL.
  • We then check if all the four link fields of M are NIL.
  • If so, we examine M’s parent (let us call it P for now). As M is P’s child, we find a link field dir1 such that P.dir1 = M. We then set P.dir1 = NIL and then (as before) check to see if P’s four link fields are all NIL.
  • if so, we continue this process.
  • Total time required for deletion is O(k).

Range Queries in MX-Quadtrees

 

Handled in exactly the same way as for point quadtrees. But there are two differences:

  • The content of the XLB,XUB,YLB,YUB fields is different from that in the case of point quadtrees.
  • As points are stored at the leaf level, checking to see if a point is in the circle denied by the range query needs to be performed only at the leaf level.

     R-Trees

 

Used to store rectangular regions of an image or a map such as those shown below. R-trees are particularly useful in storing very large amounts of data on disk. They provide a convenient way of minimizing the number of disk accesses. Each R-tree has an associated order, which is an integer K.

 

Each non-leaf R-tree node contains a set of at most K rectangles and at least K/2 rectangles (with the possible exception of the root). Intuitively, this says that each nonleaf node in the R-tree, with the exception of the root, must be at least “half” full.

 

This feature makes R-trees appropriate for disk based retrieval because each disk access brings back a page containing several (i.e. at least K/2 rectangles). R-trees manipulate two kinds of rectangles:

 

“Real” rectangles. “Group” rectangles.

This is an R-Tree of order 4, associated with the rectangles.

 

R-tree nodes have the following structure:

 

rtnodetype = record

 

Rec1,…,Reck:rectangle;

 

P1,…,Pk: ↑rtnotetype

 

end

 

Deletion in R-Trees

  • Deletion of objects from R-trees may cause a node in the R-tree to “underflow” because an R-tree of order K must contain at least K/2 rectangles (real or group) in it.
  • When we delete a rectangle from an R-tree, we must ensure that that node is not “under full.”
  • If we delete R9, then the node containing rectangle R9 would have only one node in it. In this case, we must create a new logical grouping.

One possibility is to reallocate the groups as follows:

 

 

The new R-tree is: