Spatial Data Structures

K-D Trees, PR Quadtrees

Multi-dimensional queries

Range queries

Applications

 

K-D Trees: a Generalization of BSTs

Binary Search Trees search using 1 key

Some data naturally contain multiple dimensions

Given k-dimensional data, a K-D tree indexes dimension 0 of the data at level 0, dimension 1 at level 1, etc.

 

 

Figure 13.8 (b) from book

 

 

 

Definition: the discriminator is the search key at each level i

calculation of discriminator : i mod k

Given 3-dimensional data indexed by (x,y,z),

y is the discriminator if the level number of the k-d tree is 10 since 10 mod 3 = 1

K-D Trees ….

At ith level of the tree, discriminator indexes the tree exactly as for a BST: select i mod kth coordinate of data item and compare it with i mod kth coordinate of value stored at node of K-D tree.

If (data value < node value) take-left-branch

else take-right-branch // >= case

For 2-D space, K-D tree subdivides space into rectangles. The direction of subdivision alternates among the dimensions:

 

 

Figure 13.8 (a) from book

K-D Tree Find Operation

Simple modification of BST search.

Must determine correct discriminator at each level (= level number mod k) to find out what coordinate of key to use for comparison at that level

KDNode* KD::Kdfindhelp(KDNode* rt, ELEM val, int lev, int K) const {

//lev: current level (mod K); K: number of dimensions

//dkey(val, i) returns the key value of val for dimension i

if (rt == NULL) return NULL; // Empty tree

else if (val == rt->value) return rt; // Found it

else if (dkey(val, lev) < dkey(rt->value, lev))

return Kdfindhelp(rt->left, val, (lev+1) % K, K);

else

return Kdfindhelp(rt->right, val, (lev+1) % K, K);

}

Example: find (55, 80) in

 

 

Figure 13.8 (b) from book

Deleting Nodes in a K-D Tree

Deletion similar to BST but slightly harder.

Step 1: find node to be deleted

Step 2: two cases must be handled

No children - replace ptr to node by NULL

Has children - replace node by minimum node in right subtree using KDfindmin (harder to find than in a BST!)

If no right subtree exists, then first move left subtree to become right subtree and proceed with usual delete procedure using KDfindmin

Special note: node found by KDfindmin may occur in middle of tree. Recursive call to the delete routine must be used to replace it (careful!)

KDfindmin

Must search both left and right subtrees to find minimum value for a given discriminator

KDNode* KD::KDfindmin(KDNode* rt, int discrim,

int level, int K) {

// discrim: discriminator key used for minimum search

// level: current level(mod K); K: # of levels in key

KDNode *temp1, *temp2;

if (rt == NULL) return NULL;

temp1 = KDfindmin(rt->left, discrim, (level+1)%K, K)

if (discrim != level) { //Min val could be on l/r side

temp2=KDfindmin(rt->right, discrim, (level+1)%K,K);

if((temp1 == NULL) || ((temp2 != NULL) &&

(dkey(temp2->value,discrim) <

dkey(temp1->value,discrim)))) temp1 = temp2;

//in line above, rt subtree has smaller key value

}

// temp1 has the smallest value in children (if any)

if ((temp1 == NULL) ||

(dkey(rt->value,discrim) <

dkey(temp1->value,discrim))) return rt;

else return temp1;

}

Now delete C(70, 10) from

 

Figure 13.8 (b) from book

K-D Tree Range Query

Problem: find all k-dimensional points within distance 'D' of point P

Must search through K-D tree using Euclidean distance formula

If any coordinate in the K-D tree is more than distance 'D' away from point P's corresponding coordinate, then no need to search one of the subtrees below that node.

Example: if D=10, y-coordinate of node is being examined and is 13 less than the y-coordinate of P, then no search needed of left subtree below that node

void KDRegionSearch(KDNode* rt, ELEM val, int D, int level, int K) {

// val: search key; D: search radius;

// level: current level (mod K); K: # of dimensions

// Check if record at rt is in circle

if(InCircle(key(val), D, key(rt->value)))

printout(rt->value);//Do appropriate action with node

if(dkey(rt->value,level)>(dkey(val,level)-D)//Go left

KDRegionSearch(rt->left, val, D, (level+1)%K,K);

if(dkey(rt->value,level)<(dkey(val,level)+D))//Go right

KDRegionSearch(rt->right, val, D, (level+1) % K, K); }

Function 'InCircle' uses Euclidean distance to test if point is within distance D of query point