Click here to Skip to main content
15,867,594 members
Articles / Programming Languages / SQL
Article

KD Tree - Searching in N-dimensions, Part I

Rate me:
Please Sign up or sign in to vote.
4.90/5 (26 votes)
27 Mar 20078 min read 170K   4.9K   69   16
Optimized KD-tree and multidimensional nearest neighbours search

Introduction

There is many real-life problems which requires fast analyses and fast search in multidimensional data. The most popular way used for this problem is the so called k-d tree. It has the advantage that is easy to built and has a simple algorithm for closest points and ranged search. In this article I had studied the performance of the k-d tree for nearest-neighbour search. The analyses shows that k-d works quite well for small dimensions. However the number of the searched nodes rises exponentially with the space dimension and for N>10 k-d may become too slow. Another drawback is that the bassic k-d tree do not allows balancing, you should reorder the entire tree periodically to improve it balancing, which is not convenient for changing data and large datasets. There is some extensions of k-d which makes possible run-time balancing, but the problem with the big dimensions remains as well for all k-d variations. This leaves a space for new ideas and algorithms, with this article I hope to start a discussion about the k-d enhancements and more effective solutions of the multidimensional nearest neighbour problem.

The sources contain C++ template of k-d tree and the project which I used to test the tree. If you are not familiar with the binary trees you can read my introduction article about binary trees here.

Background

First I will define the problem which the KD solves. Lets have a N-dimensional point P with coordinates Px,Py.....Pn. The point coordinates are in real orthogonal and normalized cartesian space (I suppose that the KD tree can be built for arbitrary space as long as a distance() function is provided). We search in a dataset for all points which are inside a sphere with radius R and center in the given point - ranged search, or for just one or more nearest neighbours. Note that in a N-dimensional cartesian space the distance between two points is determined by:

Image 1

where x1 and x2 are the both points coordinates and the superscript is the dimension index. It is possible to find the closest to P points as first just find all points closest to P in the first dimension, i.e. minimal (x1-x2)2 distance, then to find among them all with minimal distance in the second dimension, and so on but it will be inefficient and very slow for large datasets. Even if we built N binary trees or sorted indexes in each dimension, there is no guarantee that if the both points are too closes in one dimension they are not going to be far in other and in such way the distance between them will be large. For a ranged search with radius R this means that we should check all points inside a cube with sides NR, besides that we will had to make N binary searches for each dimension. This is almost as much inefficient as a simple sequential search through all data.

From the said above it follows that there is no simple and trivial solution of the multi-dimensional nearest neighbours problem, it can not re reduced to N one-dimensional problems and there is no N-dimensional sorting and binary search.

In 3D the problem described above is contained in the following SQL query:

SQL
SELECT * FROM Table1
WHERE SQUARE(X - X0) + SQUARE(Y - Y0) + SQUARE(Z - Y0) <= SQUARE(R0) ;

for all points inside a sphere with center (x0,y0,z0) and radius R0, and:

SQL
SELECT * FROM Table1
     WHERE ABS(X - X0) <= a/2 AND
           ABS(Y - Y0) <= a/2 AND
           ABS(Z - Y0) <= a/2  ;

for a cube with side a (Table1 contains 3 real-values columns - X,Y,z).

A typical relational database solves similar queries very inefficiently, for example in the second case it will first find all points that fulfils the first condition - ABS(X - X0) <= a/2, among them it will find all which fulfills the second condition - ABS(Y - Y0) <= a/2 and then the third - ABS(Z - Z0) <= a/2. It is almost the same to check all records, which it will do when resolves complex equations like in the first query.

To find a more efficient way to search through N-dimensional data a generalization of the Binary Tree had to be built. It is accepted this tree to be called k-d Tree. The k-d tree nodes are just as the Binary Tree, each node has Left and Right neighbour and Parent link. However,instead of one value, each node contains a multidimensional point with N coordinates and also has a axis member which defines the split plane dimension. The split dimensions are rotated from the first to the N-th, it means that the nodes from the first level of the tree are splited to left and right with respect to the first dimension (x), the second level with respect to to the second dimension (y) and so on. When the N-th level is reached the split plane index is set again to zero. The scheme below shows the k-d tree structure:

Image 2

The nodes from the first level are divided to left and right with respect to the X-axis, for a 2D space with (x,y) points this means that if x_node < x_parent, the node is placed to the left, otherwise is placed to the right. For the second level the only difference is that the split plane is y, if node_y < parent_y the node is placed to left otherwise is placed in the right. In this way the tree height rises linearly with space dimension. The problem with this depth rotation is that the tree can not be easily balanced, if we want to move a node up in the tree we had to displace nodes with different split planes, which destroys the tree dimension ordering.

Code

The declaration of k-d tree node for fixed space dimension SD is given below:

C++
//KDTNode template class declaration
KDTEMPLATE class KDNode
{
//members 
public:
    int axis ;        //split dimension
    Xtype x[SD];        //N-dimensional point 
    unsigned int id ;
    bool checked ;        //flag needed for recursive parent check

//member functions
public:
    KDNode(Xtype* x0, int split_axis);  //contructor

    KDNODE*    Insert(Xtype* x);
    KDNODE*    FindParent(Xtype* x0);

    KDNODE* Parent ;
    KDNODE* Left ;
    KDNODE* Right ;
};

The axis members is integer with values between 0 and SD-1, it contain the dimension index of the split plane. The FindParent() member function finds the parent of a target point:

C++
KDTEMPLATE
KDNODE*    KDNODE::FindParent(Xtype* x0)
{
    KDNODE* parent ;
    KDNODE* next = this ;
    int split ;
    while(next)
    {
        split = next->axis  ;
        parent = next ;
        if(x0[split] > next->x[split])
            next = next->Right ;
        else
            next = next->Left ;
    }
    return parent ;
}

Insert function links the new node and rotates the split plane index:

C++
KDTEMPLATE
KDNODE*    KDNODE::Insert(Xtype* p)
{
    KDNODE* parent = FindParent(p);
    if(equal(p, parent->x, SD))
        return NULL ;

    KDNODE* newNode = new KDNODE(p, parent->axis +1 < SD? parent->axis+1:0);
    newNode->Parent = parent ;

    if(p[parent->axis] > parent->x[parent->axis])
    {
        parent->Right = newNode ;
        newNode->orientation = 1 ;
    }
    else
    {
        parent->Left = newNode ;
        newNode->orientation = 0 ;
    }

    return newNode ;
}

Nearest Neighbours Search

The nearest neighbour to a target point not contained in the tree can be found in several ways. The most easy way is the up-down search, it first find the target parent with FindParent(). Then it determines the distance to the parent - d_min. Each node of the tree splits the space in to halfs according to it split axis, all half-spaces which overlaps with a sphere with radius < d_min and centered in the target should be checked. The up-down function starts again from the tree root and eliminate all halfspaces too far from the target:

C++
/*
   find the nearest neighbour, it start from the root 
   finds the target parent, then start again from the root and
   and eliminate all halfspaces too far from the target
*/
KDTEMPLATE
KDNODE* KDTREE::find_nearest(Xtype* x)
{
    if(!Root)
        return NULL ;

    checked_nodes = 0;

    KDNODE* parent = Root->FindParent(x);
    nearest_neighbour = parent ;
    d_min = distance2(x, parent->x, SD); ;

    if(equal(x, parent->x, SD))
        return nearest_neighbour ;

    check_subtree(Root, x);

    return nearest_neighbour ;
}

KDTEMPLATE
void KDTREE::check_subtree(KDNODE* node, Xtype* x)
{
    if(!node)
    return ;

    checked_nodes++ ;
    Xtype d = distance2(x, node->x, SD); ;
    if(d<d_min)
    {
        d_min = d;
        nearest_neighbour = node ;
    }
    
    int dim = node->axis ;
    d= node->x[dim] - x[dim];

    if (d*d > d_min) {
    if (node->x[dim] > x[dim])
      check_subtree(node->Left, x);
    else
      check_subtree(node->Right, x);
    }
    // If the distance to the target is 
    // less than the nearest distance, we still need to look
    // in both directions.
    else {
    check_subtree(node->Left, x);
    check_subtree(node->Right, x);
    }
}

The check_subtree() inspect all subtrees hyper-rectangles which are closer to the target then the current minimal distance. This eleminates all hyperrectangles which intersect the sphere and can contain child nodes closer to d_min.

However the up-down function will chech too much halfspaces when the tree root and the target point are too far away. Thus I developed a search function which start from the target parent and move up in the tree - down-up search. It uses the Parent link and goes up until the target is closed from all sides with large enough hyperrectangle, or if the tree root is reached:

C++
KDTEMPLATE
KDNODE* KDTREE::find_nearest(Xtype* x)
{
    if(!Root)
    return NULL ;

    checked_nodes = 0;

    KDNODE* parent = Root->FindParent(x);
    nearest_neighbour = parent ;
    d_min = distance2(x, parent->x, SD); ;

    if(equal(x, parent->x, SD))
        return nearest_neighbour ;

    search_parent(parent, x);
    uncheck();

    return nearest_neighbour ;
}


KDTEMPLATE
KDNODE* KDTREE::search_parent(KDNODE* parent, Xtype* x)
{
    for(int k=0; k<SD; k++)
    {
        x_min[k] = x_max[k] = 0;
        max_boundary[k] = min_boundary[k] = 0;
    }
    n_boundary = 0;

    Xtype dx;
    KDNODE* search_root = parent ;
    while(parent && n_boundary != 2*SD)
    {    
       check_subtree(parent, x);
       search_root = parent ;
       parent = parent->Parent ;
    }

    return search_root ;
}

search_parent() goes up in the tree until the number of the founded boundaries becomes bigger then 2SD or the tree parent is reached. Each parent is checked recursively from check_subtree() which changes the minimal distance and increase n_boundary when finds a node further then d_min in it split dimension. I estimated that this is sometimes more then twice faster then the up-down search. However, as I mentioned in introduction, for both methods the number of the checked nodes rises as power of 2 factor with the space dimension. Below I had plotted the number of the checked nodes for the down-up search, the tests are made for 10000 points for SD between 2 and 10:

Image 3 Image 4
For small dimensions the KD-tree can be much faster then sequential search, however for 10-dimensional space the checked nodes for rises to about 25% for. It is possible to reduce this number 2-3 times if the tree is balanced but the tendency of exponential rise of the checked nodes makes the KD unpracticle above 15 dimensions. The second curve shows how KD / Brute ratio changes with space dimension, Brute stands for sequential search, it checks all nodes. Practiclly, for 10000 points, the KD tree becomes as fast as the sequential search for dimensions bigger then 10.

With the analyses made in this article I showed that the standard KD-tree is not good for dimensions beyond 10. In my next article about KD trees and the nearest neighbours search in N-dimensions I will introduce an extention of the quad tree for N-dimensional data - QD-tree, it is faster then KD and allows run-time balancing. However for big dimensions it again becomes slow. This problem is well known in the computational geometry, this would be so for any data structure based only on tree. From another hand it is not possible to make a multidimensional linked-list and to include it in the tree. The problem is quite complicated and requires new kinds data structures.

The Test Project

To test the tree just compile the console with Visual C++ 6.0 or later MS Visual Studio and run it in release mode. The program will generate random points and will report the tree creation times, the averaged search results for KD and sequential search and the search errors if there is such:

Image 5

To modify the search for other dimensions and test point number use the following constants defined in KDtree.h:

  • SD - the space dimension
  • POINT_NUM - the random points inserted in the tree
  • TEST_NUM - the random test points used for the tests
  • KD_MAX_POINTS - change it if you want to test the tree for more then 2,000,000 points

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionThis is not a KD Tree. Pin
kevin31531512-Jul-11 15:58
kevin31531512-Jul-11 15:58 
Generalincorrect results with floating point numbers Pin
Nataliia7-Sep-10 3:26
Nataliia7-Sep-10 3:26 
QuestionK-nearest Neighbours? Pin
chickencoop7-Feb-10 20:33
chickencoop7-Feb-10 20:33 
QuestionI'm confused with your set_bounding_cube function Pin
pooh19495-Nov-09 20:49
pooh19495-Nov-09 20:49 
Generalk-nearest neighbors Pin
mirak4569726-Jan-09 16:16
mirak4569726-Jan-09 16:16 
QuestionI had a incorrect result running the program... Pin
old00020-Dec-08 3:10
old00020-Dec-08 3:10 
AnswerRe: I had a incorrect result running the program... Pin
lcsaintlee16-Apr-12 19:34
lcsaintlee16-Apr-12 19:34 
QuestionSave and Load ? Pin
Martial Spirit3-Oct-07 1:02
Martial Spirit3-Oct-07 1:02 
How to save the in-memory kdtree to a diskfile and then reload it.

Best Regards

GeneralEquation of distance Pin
Wander Costa3-Apr-07 2:27
Wander Costa3-Apr-07 2:27 
GeneralRe: Equation of distance Pin
lalakis12322-Apr-07 17:18
lalakis12322-Apr-07 17:18 
QuestionDescartes Space or Euclidean Space? Pin
jstav27-Mar-07 2:45
jstav27-Mar-07 2:45 
AnswerRe: Descartes Space or Euclidean Space? Pin
lalakis12322-Apr-07 17:04
lalakis12322-Apr-07 17:04 
GeneralName error! Pin
Costantino Grana27-Mar-07 1:26
professionalCostantino Grana27-Mar-07 1:26 
GeneralRe: Name error! Pin
tonim27-Mar-07 5:10
tonim27-Mar-07 5:10 
GeneralThanks for your explanation Pin
hiprog23-Mar-07 15:09
hiprog23-Mar-07 15:09 
GeneralRe: Thanks for your explanation Pin
tonim27-Mar-07 5:07
tonim27-Mar-07 5:07 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.