K-d tree: Difference between revisions

Line 2:

[[Category:Data Structures]]

A k-d tree (short for ''k''-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches). ~~k-d trees are a special case of binary space partitioning trees.~~

A k-d tree (short for ''k''-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches).

k-d trees are a special case of binary space partitioning trees.

k-d trees are not suitable, however, for efficiently finding the nearest neighbor in high dimensional spaces. As a general rule, if the dimensionality is ''k'', the number of points in the data, ''N'', should be ''N'' ≫ 2<sup>''k''</sup>. Otherwise, when k-d trees are used with high-dimensional data, most of the points in the tree will be evaluated and the efficiency is no better than exhaustive search, and other methods such as approximate nearest-neighbor are used instead.

k-d trees are not suitable, however, for efficiently finding the nearest neighbor in high dimensional spaces. As a general rule, if the dimensionality is ''k'', the number of points in the data, ''N'', should be ''N'' ≫ 2<sup>''k''</sup>.

Otherwise, when k-d trees are used with high-dimensional data, most of the points in the tree will be evaluated and the efficiency is no better than exhaustive search, and other methods such as approximate nearest-neighbor are used instead.

'''Task:''' Construct a k-d tree and perform a nearest neighbor search for two example data sets:

Line 16:

Line 18:

In addition, instrument your code to count the number of nodes visited in the nearest neighbor search. Count a node as visited if any field of it is accessed.

Output should show the point searched for, the point found, ~~the distance to the point, and the number of nodes visited.~~

Output should show the point searched for, the point found,

the distance to the point, and the number of nodes visited.

There are variant algorithms for constructing the tree.

There are variant algorithms for constructing the tree. You can use a simple median strategy or implement something more efficient. Variants of the nearest neighbor search include nearest N neighbors, approximate nearest neighbor, and range searches. You do not have to implement these. The requirement for this task is specifically the nearest single neighbor. Also there are algorithms for inserting, deleting, and balancing k-d trees. These are also not required for the task.

You can use a simple median strategy or implement something more efficient.

Variants of the nearest neighbor search include nearest N neighbors, approximate nearest neighbor, and range searches.

You do not have to implement these.

The requirement for this task is specifically the nearest single neighbor.

Also there are algorithms for inserting, deleting, and balancing k-d trees.

These are also not required for the task.

=={{header|C}}==

Line 194:

Line 203:

return 0;

}</lang>~~output<pre>>> WP tree~~

}</lang>

<pre>>> WP tree

searching for (9, 2)

found (8, 1) dist 1.41421

Line 420:

Line 431:

"in %d ms.", visited / double(M), M, sw.peek.msecs);

}</lang>

{{out|Output}} using the ldc2 compiler

<pre>Wikipedia example data:

Point: [9, 2]

Line 1,569:

Line 1,580:

(test 3 1000)

</lang>

Output:

Wikipedia Test