Multi-Dimensional Data
Applying Iterative Refinement in the Algorithm Design Process to handle multi-dimensional data.
1
Kevin Lin, with thanks to many others.
2-d Tree
The root node partitions entire space into left and right (x-coordinate).
All depth 1 nodes partition subspace into up and down (y-coordinate).
All depth 2 nodes partition subspace into left and right (x-coordinate).
All depth 3 nodes partition subspace into up and down (y-coordinate).
…
2
A
(2, 3)
B
(4, 2)
(4, 5)
C
D
(3, 3)
E
(1, 5)
F
(4, 4)
Which of these trees are valid 2-d trees?
3
L
R
D
U
(9, 4)
(7, 2)
(8, 0)
D
U
Q
L
R
L
R
(6, 8)
(5, 2)
(3, 7)
D
U
L
R
D
U
(5, 7)
(4, 6)
(9, 3)
L
R
KD Trees (Christine Alvarado/UCSD)
Which of these trees are valid 2-d trees?
4
L
R
D
U
(9, 4)
(7, 2)
(8, 0)
D
U
A
L
R
L
R
(6, 8)
(5, 2)
(3, 7)
D
U
L
R
D
U
(5, 7)
(4, 6)
(9, 3)
L
R
KD Trees (Christine Alvarado/UCSD)
(7,2) vs. (8,0) compares on x, invalid.
(7,2) vs. (9,4) is fine.
(5,2) vs. (6,8): recursive! Invalid.
Valid.
2-d Tree Insertion
Where would G (5, 3) go in the 2-d tree?
5
A
(2, 3)
B
(4, 2)
(4, 5)
C
D
(3, 3)
E
(1, 5)
F
(4, 4)
Q
G
(5, 3)
L
R
D
U
L
R
B (4, 2)
A (2, 3)
C (4, 5)
D (3, 3)
D
U
E (1, 5)
D
U
F (4, 4)
D
U
2-d Tree Insertion
Recursively asking: 2 vs. 5, 2 vs. 3, …
6
A
(2, 3)
B
(4, 2)
(4, 5)
C
D
(3, 3)
E
(1, 5)
F
(4, 4)
A
G
(5, 3)
L
R
D
U
L
R
B (4, 2)
A (2, 3)
C (4, 5)
D (3, 3)
D
U
E (1, 5)
D
U
F (4, 4)
D
U
Pruning the “Bad Side”
Without exploring A’s children, what is the closest possible point to (0, 7) that could exist in the subspace of A.rightChild?
Where would this node go in the 2-d tree?
7
L
R
D
U
L
R
B (4, 2)
A (2, 3)
C (4, 5)
D (3, 3)
D
U
E (1, 5)
D
U
F (4, 4)
D
U
Q
Pruning the “Bad Side”
Without exploring A’s children, what is the closest possible point to (0, 7) that could exist in the subspace of A.rightChild?
(2, 7)
Where would this node go in the 2-d tree?
D’s up-child.
8
L
R
D
U
L
R
B (4, 2)
A (2, 3)
C (4, 5)
D (3, 3)
D
U
E (1, 5)
D
U
F (4, 4)
D
U
A
Nearest Neighbor Search
Give the order in which nodes are visited in the nearest neighbor search for (0, 7).
9
Q
A
(2, 3)
B
(4, 2)
(4, 5)
C
D
(3, 3)
E
(1, 5)
F
(4, 4)
G
(5, 3)
L
R
D
U
L
R
B (4, 2)
A (2, 3)
C (4, 5)
D (3, 3)
D
U
E (1, 5)
D
U
F (4, 4)
D
U
Nearest Neighbor Search
Explore “good” side of A first: A, E.�Explore “bad” side of A next: B, C, D.
10
A
A
(2, 3)
B
(4, 2)
(4, 5)
C
D
(3, 3)
E
(1, 5)
F
(4, 4)
G
(5, 3)
L
R
D
U
L
R
B (4, 2)
A (2, 3)
C (4, 5)
D (3, 3)
D
U
E (1, 5)
D
U
F (4, 4)
D
U
Simplified pruning rule
Exact pruning rule for D
Worst-Case Input
Describe the worst-case input for a 2-d tree.
11
Q
Worst-Case Input
Describe the worst-case input for a 2-d tree.
All items are arranged in a circle and we’re looking for the nearest neighbor to the center of the circle. Since each item is about equally far from the center, we need to check every “bad” side for the potential closer nearest neighbor.
12
A