Multimedia Databases

k-dimensionl trees (k-d trees) :
Each level of a k-d tree partitions the space into two.

• choose one dimension for partitioning at the root level of the tree.
  
• choose another dimensions for partitioning in nodes at the next level and so on, cycling through the dimensions.
  

In each node, approximately half of the points stored in the sub-tree fall on one side and half on the other. Partitioning stops when a node has less than a given maximum number of points.

Each line in the figure (other than the outside box) corresponds to a node in the k-d tree. The maximum number of points in a leaf node has been set to 1.






Division of Space by Quadtrees :

Each node of a quadtree is associated with a rectangular region of space; the top node is associated with the entire target space.

Each non-leaf nodes divides its region into four equal sized quadrants correspondingly each such node has four child nodes corresponding to the four quadrants and so on. Leaf nodes have between zero and some fixed maximum number of points (set to 1 in example).




R trees :
R-trees are a N-dimensional extension of B+-trees, useful for indexing sets of rectangles and other polygons. Supported in many modern database systems, along with variants like R+ -trees and R*-trees.
A rectangular bounding box is associated with each tree node.

• Bounding box of a leaf node is a minimum sized rectangle that contains all the rectangles/polygons associated with the leaf node.
• The bounding box associated with a non-leaf node contains the bounding box associated with all its children.
• Bounding box of a node serves as its key in its parent node (if any)
• Bounding boxes of children of a node are allowed to overlap.

A polygon is stored only in one node, and the bounding box of the node must contain the polygon
The storage efficiency or R-trees is better than that of k-d trees or quadtrees since a polygon is stored only once.
To find data items (rectangles/polygons) intersecting (overlaps) a given query point/region, do the following, starting from the root node:

• If the node is a leaf node, output the data items whose keys intersect the given query point/region.
• Else, for each child of the current node whose bounding box overlaps the query point/region, recursively search the child.