Supercluster.KDTree.Standard 1.0.5

.NET Standard 1.3 .NET Framework 4.6.1
Install-Package Supercluster.KDTree.Standard -Version 1.0.5
dotnet add package Supercluster.KDTree.Standard --version 1.0.5
<PackageReference Include="Supercluster.KDTree.Standard" Version="1.0.5" />
For projects that support PackageReference, copy this XML node into the project file to reference the package.
paket add Supercluster.KDTree.Standard --version 1.0.5
The NuGet Team does not provide support for this client. Please contact its maintainers for support.
#r "nuget: Supercluster.KDTree.Standard, 1.0.5"
#r directive can be used in F# Interactive, C# scripting and .NET Interactive. Copy this into the interactive tool or source code of the script to reference the package.
// Install Supercluster.KDTree.Standard as a Cake Addin
#addin nuget:?package=Supercluster.KDTree.Standard&version=1.0.5

// Install Supercluster.KDTree.Standard as a Cake Tool
#tool nuget:?package=Supercluster.KDTree.Standard&version=1.0.5
The NuGet Team does not provide support for this client. Please contact its maintainers for support.

Supercluster.KDTree

This is a KD-Tree written completely in C#. This project originally started as a fork of the KD-Tree Written by CodeandCats, however, the structure and intention of this project has changed drastically from its origin.

About the Project

This is a KD-Tree that is optimized for machine learning applications, however, it can used for less intensive purposes as well. (In fact, I am writing this for my machine learning library Supercluster) In machine learning data-sets are often built, re-built, and built again. Also, in machine learning, algorithms need to be fast for look ups but it is more acceptable to be slow for construction. Thus the tree bas been designed with this philosophy in mind. General characteristics are:

  • The tree is extremely fast for search.

    • 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. This is slower than the quickselect or median-of-medians algorithm but is more likely to create a balanced tree. This allows for search time to be as close to O(log n) as possible.
  • There is no delete method. If you want to change the tree, rebuild it. Many KD-Tree implementations simply rebuild the tree to "balance" the tree after deletion. 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, look it up if you need one.

  • 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:

Special Thanks
  • 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.
Product Versions
.NET net5.0 net5.0-windows net6.0 net6.0-android net6.0-ios net6.0-maccatalyst net6.0-macos net6.0-tvos net6.0-windows
.NET Core netcoreapp1.0 netcoreapp1.1 netcoreapp2.0 netcoreapp2.1 netcoreapp2.2 netcoreapp3.0 netcoreapp3.1
.NET Standard netstandard1.3 netstandard1.4 netstandard1.5 netstandard1.6 netstandard2.0 netstandard2.1
.NET Framework net46 net461 net462 net463 net47 net471 net472 net48
MonoAndroid monoandroid
MonoMac monomac
MonoTouch monotouch
Tizen tizen30 tizen40 tizen60
Universal Windows Platform uap uap10.0
Xamarin.iOS xamarinios
Xamarin.Mac xamarinmac
Xamarin.TVOS xamarintvos
Xamarin.WatchOS xamarinwatchos
Compatible target framework(s)
Additional computed target framework(s)
Learn more about Target Frameworks and .NET Standard.

NuGet packages

This package is not used by any NuGet packages.

GitHub repositories

This package is not used by any popular GitHub repositories.

Version Downloads Last updated
1.0.5 5,611 12/24/2020