# Simple Unbalanced KDTree with 1NN Implementation

This is our first attempt at building an unbalanced k-dimensional tree with nearest neighbor (1NN) lookup to process multi-dimensional data. In particular, the "suspect region" in the NN() function is where we are having the most questions:

• Is a distance calculation (distCheck) necessary on every element in the subtree to assure the nearest candidate point? Is there a more elegant way to do this given the $O(log n)$ nature of kdtrees?
• While we could readily find code for "search" (exact match) implementations, we struggled to find examples of 1NN implementations. From what we've gathered, search is very similar to sort with an added parameter of comparing radii:

• Compare the given point's current working dimension to the root node's corresponding dimension; if < recursively search the left sub tree, if >= recursively search the right sub tree.
• After recursion, if the radius from the given point's current dimension to the opposing subtree's corresponding dimension is <= the radius to the root node, recurse the opposing subtree as well.

Is this properly implemented? It seems unnecessarily verbose, given the nature of the data-structure. Clearly this could benefit from templatization and variable truncation, but are there more elegant approaches to this functionality?

The node struct:

#include<iostream>
#include<cmath>

struct kdNode {
kdNode(unsigned int k) {
point = new float[k];
left = NULL;
right = NULL;
dim = k;
}
float *point;   // The point in k-space
kdNode *left;   // less-than node
kdNode *right;   // greater-than-or-equal node
unsigned int dim;   // k

friend std::ostream &operator<<(std::ostream &outStream, kdNode &node){
outStream << "(";
for (int i = 0; i < (node.dim - 1); i++) {
outStream << node.point[i];
outStream << ",";
}
return outStream << node.point[node.dim - 1] << ")";
}
};


And functions:

kdNode *insert(kdNode *parentNode, float point[], unsigned int currDepth, unsigned int dim)
{
// Inserts a node (sorted, but unbalanced)
if (parentNode == NULL){
kdNode *temp = new kdNode(dim);
for (int i = 0; i < dim; i++)
temp->point[i] = point[i];
return temp;
}

unsigned workingDepth = currDepth % dim;

if (point[workingDepth] < (parentNode->point[workingDepth]))
parentNode->left  = insert(parentNode->left, point, currDepth + 1, dim);
else
parentNode->right = insert(parentNode->right, point, currDepth + 1, dim);

return parentNode;
}

void distCheck(kdNode *currNode, float point[], kdNode *&candidateNode){
// Checks distance and manipulates the nearest candidate node

float currNodeDist = 0;
float candidateNodeDist = 0;

for(int i = 0; i < currNode->dim; i++)
{
float norm1 = point[i] - currNode->point[i];
float norm2 = point[i] - candidateNode->point[i];
currNodeDist += norm1 * norm1;
candidateNodeDist += norm2 * norm2;
}
candidateNode = (candidateNodeDist < currNodeDist)?candidateNode:currNode;
return;
}

void NN(kdNode *currNode, float point[], kdNode *&candidateNode, unsigned int currDepth)
{
// Finds nearest neighbor
if (currNode == NULL)
return;

unsigned workingDepth = currDepth % currNode->dim;

//Suspect region
distCheck(currNode, point, candidateNode);

if (point[workingDepth] < currNode->point[workingDepth]) {
NN(currNode->left, point, candidateNode, currDepth + 1);
if((currNode->right != NULL) && std::abs(point[workingDepth] - currNode->point[workingDepth]) >= std::abs(point[workingDepth] - currNode->right->point[workingDepth]))
NN(currNode->right, point, candidateNode, currDepth + 1);
}
else {
NN(currNode->right, point, candidateNode, currDepth + 1);
if ((currNode->left != NULL) && std::abs(point[workingDepth] - currNode->point[workingDepth]) >= std::abs(point[workingDepth] - currNode->left->point[workingDepth]))
NN(currNode->left, point, candidateNode, currDepth + 1);
}
// End suspect region
return;
}


Some sample use:

int main()
{
// This will eventually be a linked-list
float points[] = {{1.9,1}, {1,2}, {2.1,3.1}, {0.9,0.9}, {1.5,3.5}, {2.9,2.1}, {3,4}, {0,0}, {1.7,2.7}, {4,3}, {2,5}};
unsigned int dim = 2;
unsigned int numOfPts = sizeof(points)/sizeof(points);

kdNode *kdtree = NULL;

for (int i = 0; i < numOfPts; i++)
kdtree = insert(kdtree, points[i], 0, dim);

float point1[] = {3,3};

std::cout << "\n(" << point1 << "," <<  point1 << ") ";
kdNode *near = kdtree;
NN(kdtree, point2, near, 0);
std::cout << "Nearest node ";
std::cout << *near;
return 0;
}