Multimedia data structures

2d, 3d, space-time

multimedia data -- reasoning about time and space
n-dimensional data -- attributes from n-dim space

slide: Multimedia data structures

Hierarchical decompositions -- tree

k-d tree
point quad tree
MX quad tree
R-trees
TV trees

slide: Hierarchical decomposition

k-d trees -- node structure $(k = 2)$


  nodetype = record
    info : infotype;
    xval : real;
    yval : real;
    llink : *nodetype;
    rlink : *nodetype;
  end

slide: k-d trees -- node structure

Definition


  	    0             if N is the root
  level(N) =
  	    level(P) + 1  if N's parent is P

Conditions


  level(N) even:  L is subtree at N.llink: L.xval < N.xval
  		R is subtree at N.rlink: R.xval >= N.xval
    
  level(N) odd:   L is subtree at N.llink: L.yval < N.yval
  		R is subtree at N.rlink: R.yval >= N.yval

slide: Definition and constraints

Insertion -- node N


   try T, level(T) is even


   if T.xval = N.xval & T.yval = N.yval then T = N;
   else if N.xval < T.val then branch left
   else if N.xval >= T.val then branch right

Search

similar

slide: Insertion

Deletion -- node N


    1. search for node N
    2. if N is leaf, delete
       else 
        1. find candidate replacement node K in T1, i e {l,r}
        2. replace N's non-links fields by those of K
        3. delete K from Ti

slide: Deletion

Conditions -- K must satisfy


    1. level(N) even: 
  	all L in Tl, L.xval < K.xval
          all R in Tr, R.xval >= K.xval
  
    2. level(N) odd :
  	all L in Tl, L.yval < K.yval
          all R in Tr, R.yval >= K.yval

Heuristics - right subtree, Tr not empty

label(N) even, node with smallest xval in Tr
label(N) odd, node with smallest yval in Tr

left subtree

maximal xval or yval, must be unique

slide: Conditions -- replacement node

Range queries

a range query wrt. a 2-d tree T is a query that specifies a point $(x_c,y_c)$ and distance r

Answer

set of all points $(x,y) $s.t. $(x,y)$ within distance r from $(x_c,y_c)

slide: Range queries

Range and nodes

each node in a 2-d tree implicitly represents a region $R_N$ .
in general, each node N has at most four associated constraints that jointly define the region represented by that node.

Region


     XLB: x >= c1; XUB: x < c2; YLB: y >= c3; XUB: y < c4;

slide: Ranges and nodes

slide: Regions and bounds

Conditions

1. root: XLB = YLB = -inf; XUB = YUB = inf
2. node N has node P as its parent and level(P) is even:


    N.xlb = P.xlb  if N = P.llink
    N.xlb = P.xval if N = P.rlink
    N.xub = P.xval if N = P.llink
    N.xub = P.xub  if N = P.rlink
    N.ylb = P.ylb; N.yub = P.yub

3. node N has node P as its parent and level(P) is odd:


    N.ylb = P.ylb  if N = P.llink
    N.ylb = P.yval if N = P.rlink
    N.yub = P.yval if N = P.llink
    N.yub = P.yub  if N = P.rlink
    N.xlb = P.xlb; N.xub = P.xub

slide: Bounds -- conditions