kd-tree
| This article is a stub. You can help RoboWiki by expanding it. |
In computer science, a kd-tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. kd-trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbour searches). kd-trees are a special case of BSP trees.
In Robocode, a kd-tree is a data structure use for k-nearest neighbours searching in Dynamic Clustering data logging algorithms. Currently, the most popular type of kd-tree in Robocode is the Bucket PR kd-tree.
How it works?
Please complete this section if you can (about real kd-tree, not bucket PR kd-tree)
Bucket PR kd-tree
Bucket PR kd-trees have two characteristics:
- Bucket means points are collected in leaves until they overflow. Only then are they split. This makes the tree more likely to be balanced since we can choose a smarter splitting point than whatever we receive first.
- PR means the tree cycles through split dimensions in a constant order. This is faster to calculate than other strategies like splitting on the dimension with the largest variance.
For an applet demo, see Spatial Index Demos. The example there splits on the middle of the rectangle covered by a bucket, while most authors split on the median of the points in a bucket.
Implementations
There are several implementation of kd-tree around today, and most if not all of them are bucket PR kd-trees:
- Rednaxela's kd-tree: The fastest and most efficient kd-tree around today.
- Voidious's kd-tree: The second-to-top tree.
- Simonton's kd-tree: The first bucket PR kd-tree in Robocode community.
