[]
readme
course(s)
preface
I
1
2
II
3
4
III
5
6
7
IV
8
9
10
V
11
12
afterthought(s)
appendix
reference(s)
example(s)
resource(s)
_

** 2d, 3d, space-time**

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

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

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

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

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

## 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

try T, level(T) is even

*similar*

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

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

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

- maximal
*xval*or*yval*, must be unique

- a range query wrt. a 2-d tree T is a query that specifies a point $(x\_c,y\_c)$ and distance
*r*

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

- 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.

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

- 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

[]
readme
course(s)
preface
I
1
2
II
3
4
III
5
6
7
IV
8
9
10
V
11
12
afterthought(s)
appendix
reference(s)
example(s)
resource(s)
_

(C) Æliens 04/09/2009

You may not copy or print any of this material without explicit permission of the author or the publisher. In case of other copyright issues, contact the author.