Difference between revisions of "Kd-tree"
m (→Implementations: add link to [[Range Search[[) |
(→Implementations: add Duyn's, update description of Void's) |
||
| Line 17: | Line 17: | ||
There are several implementations of kd-tree around Robocode's community, and most if not all of them are bucket PR kd-trees: | There are several implementations of kd-tree around Robocode's community, and most if not all of them are bucket PR kd-trees: | ||
* [[User:Rednaxela/kD-Tree|Rednaxela's kd-tree]]: The fastest and most efficient kd-tree around today. | * [[User:Rednaxela/kD-Tree|Rednaxela's kd-tree]]: The fastest and most efficient kd-tree around today. | ||
| − | * [[Diamond/Code|Voidious' | + | * [[User:Duyn/BucketKdTree|Duyn's kd-tree]]: Another highly optimized kd-tree implementation. See also [[User:Duyn/kd-tree Tutorial|Duyn's kd-tree tutorial]]. |
| + | * [[Diamond/Code|Voidious' kd-tree]]: A fairly primitive but functional kd-tree. | ||
* [[User:Chase-san/Kd-Tree|Chase's KD-TreeC]]: A fair tree and the only one that includes [[Range Search|range searching]]. | * [[User:Chase-san/Kd-Tree|Chase's KD-TreeC]]: A fair tree and the only one that includes [[Range Search|range searching]]. | ||
* Simonton's kd-tree: The first bucket PR kd-tree in Robocode community. | * Simonton's kd-tree: The first bucket PR kd-tree in Robocode community. | ||
Revision as of 19:50, 19 August 2011
| 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:
- Rednaxela's kd-tree: The fastest and most efficient kd-tree around today.
- Duyn's kd-tree: Another highly optimized kd-tree implementation. See also Duyn's kd-tree tutorial.
- Voidious' kd-tree: A fairly primitive but functional kd-tree.
- Chase's KD-TreeC: A fair tree and the only one that includes range searching.
- Simonton's kd-tree: The first bucket PR kd-tree in Robocode community.
