Multidimensional Data Structures © 2002, Arry Akhmad Arman Laboratory for Signal & Systems Electrical Engineering Department Bandung Institute of Technology email :
[email protected]
¿
N-dimensional Data z Most media data requires the ability to reason about both time and space. z Such data is typically referred to as n-dimensional data,
reflection the fact that data has associated attributes drawn from n-dimensional space. Example : o Typical two dimensional coordinates (x, y) o Three dimensional coordinates (x, y, z) o Space time (x, y, z, t)
z Most techniques to store n-dimensional data do by using “hierarchical” decomposition of space that are typically represented by various kind of trees : k-d trees, point quadtrees, MX quadtrees, and R-trees.
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
2
K-d Trees : Introduction z The k-d trees is used to
store k-dimensional point data such as that shown in figure below. z For k=2, k-d tree is 2-d tree z For k-3, k-d tree is 3-d tree
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
3
K-d Trees : Node Structure nodetype = record INFO : infotype; XVAL : real; YVAL : real; LLINK : ^infotype; RLINK : ^infotype; end;
INFO LLINK
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
XVAL YVAL RLINK
4
K-d Trees : Rules (1) z 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 define as Level(N) = 0 if N is the root of the tree Level(N) = level(P)+1 if N’s parent is P
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
5
K-d Trees : Rules (2) z If N is a node in the tree such that level(N) is even, then o every node M in th subtree rooted at N.LLINK has the propeeerty that M.XVAL < M.XVAL, o every node P in th subtree rooted at N.RLINK has the propeeerty that P.XVAL >= P.XVAL,
z If N is a node in the tree such that level(N) is odd, then o every node M in th subtree rooted at N.LLINK has the propeeerty that M.YVAL < M.YVAL, o every node P in th subtree rooted at N.RLINK has the propeeerty that P.YVAL < P.YVAL,
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
6
K-d Tree : Insertion City (XVAL, YVAL) Banja Luka (19, 45) Derventa (40, 50) Teslic (38, 38) Tuzla (54, 40) Sinj (4,4)
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
7
K-d Tree : Insertion (2)
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
8
K-d Tree : Characteristics z Tree structure dipengaruhi oleh urutan pemasukan node z Titik yang sesungguhnya direpresentasikan dengan setiap
node pada tree z Setiap node selalu berisi informasi (tidak ada node perantara yang kosong) z Setiap node informasi mungkin terletak diujung tree, diawal (root) atau ditengah. Hal ini akan menyulitkan proses deletion jika node yang akan dihapus tidak terletak di ujung.
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
9
Point Quad Tree : Node Structure nodetype = record INFO : infotype; XVAL : real; YVAL : real; NW : ^infotype; SW : ^infotype; NE : ^infotype; SE : ^infotype; end; INFO NW
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
SW
XVAL
YVAL
NE
SE
10
Point Quad Tree : Rules (1)
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
11
Point Quad Tree : Rules (2)
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
12
Point Quad Tree : Insertion City (XVAL, YVAL) Banja Luka (19, 45) Derventa (40, 50) Teslic (38, 38) Tuzla (54, 40) Sinj (4,4)
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
13
Point Quad Tree : Insertion (2)
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
14
Point Quad Tree : Characteristics z Tree structure dipengaruhi oleh urutan pemasukan node z Titik yang sesungguhnya direpresentasikan dengan setiap
node pada tree z Setiap node selalu berisi informasi (tidak ada node perantara yang kosong) z Setiap node informasi mungkin terletak diujung tree, diawal (root) atau ditengah. Hal ini akan menyulitkan proses deletion jika node yang akan dihapus tidak terletak di ujung. z Kedalaman tree lebih pendek dibandingkan k-d tree
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
15
MX Quad Tree : Node Structure nodetype = record INFO : infotype; XVAL : real; YVAL : real; NW : ^infotype; SW : ^infotype; NE : ^infotype; SE : ^infotype; end; INFO NW
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
SW
XVAL
YVAL
NE
SE
16
MX Quad Tree : Rules (1)
© 1999-2001, ARRY AKHMAD ARMAN - Electrical Engineering Dept. of ITB
17
