Supercluster.KDTree.Net 1.0.22

Supercluster.KDTree

This is a KD-Tree written completely in C#. This project originally started as a fork of the KD-Tree Written by Eric Regina. This effort is simply updating the code to be more idiomatic C# and to add some additional features.

About the Project

This is a KD-Tree that was originally optimized for machine learning applications, by the original author (Supercluster)

• The tree is fast in searching, but it is not modifiable.

  • For a 10,000 3-nearest-neighbor searches on a 1,000,000 node 2-Dimensional tree using floats is about 7.5 times than the KD-Tree by CodeandCats (number based off of a 1,000,000 sample independent T-test for mean comparisons, equal variance assumed).
  • The nearest-neighbor list is a custom data structure (called a BoundedPriorityList) that remains sorted and has O(log n) insert, but it is often much faster than O(log n) as an item is ignored if it is larger than the lists current max-element.
  • Utilizes .NET's new aggressive inlining optimization where appropriate.
  • The KD-Tree is implemented as an array. Index arithmetic is used to traverse nodes. This is faster (only slightly, but a statistically significant difference) than traversing node objects. This also leads to less memory usage.
  • The tree is built in the standard-way using an exact median finding algorithm. In this latest fork/version, a median finding approach is implemented to speed up the creation of the KD-Tree, the search times are, of course, unaffected as the resulting tree is the same.

• There is no delete and add method. If you want to change the tree, rebuild it. Many KD-Tree implementations simply rebuild the tree to "balance" the tree after a CRUD operation. This is because balancing a KD-Tree is much more complicated than AVL or Red-Black trees. There do exist adaptive KD-Trees which auto-balance, but the time to do so may not be worth it. As generation is fairly quick here.

• There is no node object used in the KDTree class. but there is a NodeNavigator class which allows you to traverse the tree (or any array) using familiar, left, right, parent properties of a node.

• The tree is generic. Only IComparable<T> is required.

• The tree requires a metric (a distance measure function) Func. KD-Trees are spatial data-structures and one only needs a metric function to implicitly define the metric space in which the KD-Tree lives.

• The code is unit tested and well documented. Style-cop, unit-test, wiki tutorials and MSDN style docs. It's all here.

Documentation and Tutorial:

• MSDN Style Documentation: http://eric-regina.github.io/Supercluster.KDTree
• Wiki and Tutorials: https://github.com/eric-regina/Supercluster.KDTree/wiki
• Nuget Package: Install-Package Supercluster.KDTree.Net

Special Thanks

• Thanks to Eric Regina who did all the hard work 5 years ago.
• Thanks to CodeandCats for the original implementation that this was based off. I had fun tearing apart reading your code. 😉
• Thanks to Prof. Hanan Samet for writing an amazing book on spatial and metric data structures. The book provided much insight and knowledge.
• Thanks to César Souza for your work on machine learning for .NET. It has inspired me to try and do better!
• Also a small thanks to BlueRaja. While I didn't use any of your code your high speed priority queue inspired me to write my own custom data structure for the nearest-neighbor list which turned out to be way faster than any "off the shelf" solution.