kd-tree

From Robowiki
Revision as of 14:16, 8 August 2011 by Nat (talk | contribs) (→‎Implementations: add link to [[Range Search[[)
Jump to navigation Jump to search
Wikipedia
Wikipedia has an article about:
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 stands for Point-Region. The tree recursively splits its region into two equally-sized areas, regardless of the position of the actual data, until buckets no longer overflow. This is more likely to retain balance if the data is evenly distributed since the final tree does not depend on the order of the data. If the data is closely clustered, however, this can result in an excessively deep tree.

For an applet demo, see Spatial Index Demos. The example there cycles partitioning axes in a fixed order, while most authors use a more intelligent algorithm. Rednaxela's kd-tree, for example, splits on the widest dimension.

Implementations

There are several implementations of kd-tree around Robocode's community, and most if not all of them are bucket PR kd-trees:

See also