In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, a ''k''-d tree (short for ''k-dimensional
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
'') is a
space-partitioning data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
for organizing
point
Point or points may refer to:
Places
* Point, Lewis, a peninsula in the Outer Hebrides, Scotland
* Point, Texas, a city in Rains County, Texas, United States
* Point, the NE tip and a ferry terminal of Lismore, Inner Hebrides, Scotland
* Point ...
s in a ''k''-dimensional
space
Space is the boundless three-dimensional extent in which objects and events have relative position and direction. In classical physics, physical space is often conceived in three linear dimensions, although modern physicists usually consider ...
. ''k''-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g.
range search
In computer science, the range searching problem consists of processing a set ''S'' of objects, in order to determine which objects from ''S'' intersect with a query object, called the ''range''. For example, if ''S'' is a set of points correspond ...
es and
nearest neighbor search
Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function ...
es) and creating
point clouds
Point or points may refer to:
Places
* Point, Lewis, a peninsula in the Outer Hebrides, Scotland
* Point, Texas, a city in Rains County, Texas, United States
* Point, the NE tip and a ferry terminal of Lismore, Inner Hebrides, Scotland
* Point ...
. ''k''-d trees are a special case of
binary space partitioning
In computer science, binary space partitioning (BSP) is a method for space partitioning which recursively subdivides a Euclidean space into two convex sets by using hyperplanes as partitions. This process of subdividing gives rise to a represen ...
trees.
Description
The ''k''-d tree is a
binary tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
in which ''every'' node is a ''k''-dimensional point. Every non-leaf node can be thought of as implicitly generating a splitting
hyperplane
In geometry, a hyperplane is a subspace whose dimension is one less than that of its ''ambient space''. For example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hyper ...
that divides the space into two parts, known as
half-spaces. Points to the left of this hyperplane are represented by the left subtree of that node and points to the right of the hyperplane are represented by the right subtree. The hyperplane direction is chosen in the following way: every node in the tree is associated with one of the ''k'' dimensions, with the hyperplane perpendicular to that dimension's axis. So, for example, if for a particular split the "x" axis is chosen, all points in the subtree with a smaller "x" value than the node will appear in the left subtree and all points with a larger "x" value will be in the right subtree. In such a case, the hyperplane would be set by the x value of the point, and its
normal Normal(s) or The Normal(s) may refer to:
Film and television
* ''Normal'' (2003 film), starring Jessica Lange and Tom Wilkinson
* ''Normal'' (2007 film), starring Carrie-Anne Moss, Kevin Zegers, Callum Keith Rennie, and Andrew Airlie
* ''Norma ...
would be the unit x-axis.
Operations on ''k''-d trees
Construction
Since there are many possible ways to choose axis-aligned splitting planes, there are many different ways to construct ''k''-d trees. The canonical method of ''k''-d tree construction has the following constraints:
* As one moves down the tree, one cycles through the axes used to select the splitting planes. (For example, in a 3-dimensional tree, the root would have an ''x''-aligned plane, the root's children would both have ''y''-aligned planes, the root's grandchildren would all have ''z''-aligned planes, the root's great-grandchildren would all have ''x''-aligned planes, the root's great-great-grandchildren would all have ''y''-aligned planes, and so on.)
* Points are inserted by selecting the
median
In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population, or a probability distribution. For a data set, it may be thought of as "the middle" value. The basic fe ...
of the points being put into the
subtree
In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be con ...
, with respect to their coordinates in the axis being used to create the splitting plane. (Note the assumption that we feed the entire set of ''n'' points into the algorithm up-front.)
This method leads to a
balanced
In telecommunications and professional audio, a balanced line or balanced signal pair is a circuit consisting of two conductors of the same type, both of which have equal impedances along their lengths and equal impedances to ground and to other ...
''k''-d tree, in which each leaf node is approximately the same distance from the root. However, balanced trees are not necessarily optimal for all applications.
Note that it is not ''required'' to select the median point. In the case where median points are not selected, there is no guarantee that the tree will be balanced. To avoid coding a complex
median-finding algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
or using an
sort such as
heapsort
In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the ...
or
mergesort
In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same ...
to sort all ''n'' points, a popular practice is to sort a ''fixed'' number of ''randomly'' ''selected'' points, and use the median of those points to serve as the splitting plane. In practice, this technique often results in nicely balanced trees.
Given a list of ''n'' points, the following algorithm uses a median-finding sort to construct a balanced ''k''-d tree containing those points.
function kdtree (''list of points'' pointList, ''int'' depth)
It is common that points "after" the median include only the ones that are strictly greater than the median in the current dimension. For points that lie on the median in the current dimension, it is possible to define a function that compares them in all dimensions. In some cases, it is acceptable to let points equal to the median lie on one side of the median, for example, by splitting the points into a "lesser than" subset and a "greater than or equal to" subset.
This algorithm creates the
invariant
Invariant and invariance may refer to:
Computer science
* Invariant (computer science), an expression whose value doesn't change during program execution
** Loop invariant, a property of a program loop that is true before (and after) each iteratio ...
that for any node, all the nodes in the left
subtree
In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be con ...
are on one side of a splitting
plane
Plane(s) most often refers to:
* Aero- or airplane, a powered, fixed-wing aircraft
* Plane (geometry), a flat, 2-dimensional surface
Plane or planes may also refer to:
Biology
* Plane (tree) or ''Platanus'', wetland native plant
* ''Planes' ...
, and all the nodes in the right subtree are on the other side. Points that lie on the splitting plane may appear on either side. The splitting plane of a node goes through the point associated with that node (referred to in the code as ''node.location'').
Alternative algorithms for building a balanced presort the data prior to building the tree. Then, they maintain the order of the presort during tree construction and hence eliminate the costly step of finding the median at each level of subdivision. Two such algorithms build a balanced to sort triangles in order to improve the execution time of
ray tracing for three-dimensional
computer graphics
Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
. These algorithms presort ''n'' triangles prior to building the , then build the tree in
time in the best case. An algorithm that builds a balanced to sort points has a worst-case complexity of
.
This algorithm presorts ''n'' points in each of ''k'' dimensions using an
sort such as
Heapsort
In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the ...
or
Mergesort
In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same ...
prior to building the tree. It then maintains the order of these ''k'' presorts during tree construction and thereby avoids finding the median at each level of subdivision.
Example implementation
The above algorithm implemented in the
Python programming language
Python is a high-level, general-purpose programming language. Its design philosophy emphasizes code readability with the use of significant indentation.
Python is dynamically-typed and garbage-collected. It supports multiple programming p ...
is as follows:
from collections import namedtuple
from operator import itemgetter
from pprint import pformat
class Node(namedtuple("Node", "location left_child right_child")):
def __repr__(self):
return pformat(tuple(self))
def kdtree(point_list, depth: int = 0):
if not point_list:
return None
k = len(point_list # assumes all points have the same dimension
# Select axis based on depth so that axis cycles through all valid values
axis = depth % k
# Sort point list by axis and choose median as pivot element
point_list.sort(key=itemgetter(axis))
median = len(point_list) // 2
# Create node and construct subtrees
return Node(
location=point_list edian
left_child=kdtree(point_listmedian
In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population, or a probability distribution. For a data set, it may be thought of as "the middle" value. The basic fe ...
depth + 1),
right_child=kdtree(point_list edian + 1 : depth + 1),
)
def main():
"""Example usage"""
point_list = 7, 2), (5, 4), (9, 6), (4, 7), (8, 1), (2, 3) tree = kdtree(point_list)
print(tree)
if __name__ "__main__":
main()
Output would be:
((7, 2),
((5, 4), ((2, 3), None, None), ((4, 7), None, None)),
((9, 6), ((8, 1), None, None), None))
The generated tree is shown below.
Adding elements
One adds a new point to a ''k''-d tree in the same way as one adds an element to any other
search tree
In computer science, a search tree is a tree data structure used for locating specific keys from within a set. In order for a tree to function as a search tree, the key for each node must be greater than any keys in subtrees on the left, and less ...
. First, traverse the tree, starting from the root and moving to either the left or the right child depending on whether the point to be inserted is on the "left" or "right" side of the splitting plane. Once you get to the node under which the child should be located, add the new point as either the left or right child of the leaf node, again depending on which side of the node's splitting plane contains the new node.
Adding points in this manner can cause the tree to become unbalanced, leading to decreased tree performance. The rate of tree performance degradation is dependent upon the spatial distribution of tree points being added, and the number of points added in relation to the tree size. If a tree becomes too unbalanced, it may need to be re-balanced to restore the performance of queries that rely on the tree balancing, such as nearest neighbour searching.
Removing elements
To remove a point from an existing ''k''-d tree, without breaking the invariant, the easiest way is to form the set of all nodes and leaves from the children of the target node, and recreate that part of the tree.
Another approach is to find a replacement for the point removed. First, find the node
that contains the point to be removed. For the base case where R is a leaf node, no replacement is required. For the general case, find a replacement point, say
, from the subtree rooted at
. Replace the point stored at
with
. Then, recursively remove
.
For finding a replacement point, if
discriminates on
(say) and
has a right child, find the point with the minimum
value from the subtree rooted at the right child. Otherwise, find the point with the maximum
value from the subtree rooted at the left child.
Balancing
Balancing a ''k''-d tree requires care because ''k''-d trees are sorted in multiple dimensions so the
tree-rotation technique cannot be used to balance them as this may break the invariant.
Several variants of balanced ''k''-d trees exist. They include divided ''k''-d tree, pseudo ''k''-d tree,
K-D-B-tree, hB-tree and
Bkd-tree. Many of these variants are
adaptive k-d trees.
Nearest neighbour search
The
nearest neighbour search
Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function ...
(NN) algorithm aims to find the point in the tree that is nearest to a given input point. This search can be done efficiently by using the tree properties to quickly eliminate large portions of the search space.
Searching for a nearest neighbour in a ''k''-d tree proceeds as follows:
# Starting with the root node, the algorithm moves down the tree recursively, in the same way that it would if the search point were being inserted (i.e. it goes left or right depending on whether the point is lesser than or greater than the current node in the split dimension).
# Once the algorithm reaches a leaf node, it checks the node point and if the distance is better than the "current best", that node point is saved as the "current best".
# The algorithm unwinds the recursion of the tree, performing the following steps at each node:
## If the current node is closer than the current best, then it becomes the current best.
## The algorithm checks whether there could be any points on the other side of the splitting plane that are closer to the search point than the current best. In concept, this is done by intersecting the splitting
hyperplane
In geometry, a hyperplane is a subspace whose dimension is one less than that of its ''ambient space''. For example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hyper ...
with a
hypersphere
In mathematics, an -sphere or a hypersphere is a topological space that is homeomorphic to a ''standard'' -''sphere'', which is the set of points in -dimensional Euclidean space that are situated at a constant distance from a fixed point, cal ...
around the search point that has a radius equal to the current nearest distance. Since the hyperplanes are all axis-aligned this is implemented as a simple comparison to see whether the distance between the splitting coordinate of the search point and current node is lesser than the distance (overall coordinates) from the search point to the current best.
### If the hypersphere crosses the plane, there could be nearer points on the other side of the plane, so the algorithm must move down the other branch of the tree from the current node looking for closer points, following the same recursive process as the entire search.
### If the hypersphere doesn't intersect the splitting plane, then the algorithm continues walking up the tree, and the entire branch on the other side of that node is eliminated.
# When the algorithm finishes this process for the root node, then the search is complete.
Generally the algorithm uses squared distances for comparison to avoid computing square roots. Additionally, it can save computation by holding the squared current best distance in a variable for comparison.
The algorithm can be extended in several ways by simple modifications. It can provide the ''k'' nearest neighbours to a point by maintaining ''k'' current bests instead of just one. A branch is only eliminated when ''k'' points have been found and the branch cannot have points closer than any of the ''k'' current bests.
It can also be converted to an approximation algorithm to run faster. For example, approximate nearest neighbour searching can be achieved by simply setting an upper bound on the number points to examine in the tree, or by interrupting the search process based upon a real time clock (which may be more appropriate in hardware implementations). Nearest neighbour for points that are in the tree already can be achieved by not updating the refinement for nodes that give zero distance as the result, this has the downside of discarding points that are not unique, but are co-located with the original search point.
Approximate nearest neighbour is useful in real-time applications such as robotics due to the significant speed increase gained by not searching for the best point exhaustively. One of its implementations is
best-bin-first search.
Range search
A range search searches for ranges of parameters. For example, if a tree is storing values corresponding to income and age, then a range search might be something like looking for all members of the tree which have an age between 20 and 50 years and an income between 50,000 and 80,000. Since k-d trees divide the range of a domain in half at each level of the tree, they are useful for performing range searches.
Analyses of binary search trees has found that the worst case time for range search in a ''k''-dimensional ''k''-d tree containing ''n'' nodes is given by the following equation.
:
Degradation in performance with high-dimensional data
Finding the nearest point is an
operation on average, in the case of randomly distributed points, although analysis in general is tricky.
In high-dimensional spaces, the
curse of dimensionality
The curse of dimensionality refers to various phenomena that arise when analyzing and organizing data in high-dimensional spaces that do not occur in low-dimensional settings such as the three-dimensional physical space of everyday experience. The ...
causes the algorithm to need to visit many more branches than in lower-dimensional spaces. In particular, when the number of points is only slightly higher than the number of dimensions, the algorithm is only slightly better than a linear search of all of the points. As a general rule, if the dimensionality is ''k'', the number of points in the data, ''n'', should be
. Otherwise, when ''k''-d trees are used with high-dimensional data, most of the points in the tree will be evaluated and the efficiency is no better than exhaustive search, and, if a good-enough fast answer is required, approximate nearest-neighbour methods should be used instead.
Degradation in performance when the query point is far from points in the ''k''-d tree
Additionally, even in low-dimensional space, if the average pairwise distance between the ''k'' nearest neighbors of the query point is significantly less than the average distance between the query point and each of the ''k'' nearest neighbors, the performance of nearest neighbor search degrades towards linear, since the distances from the query point to each nearest neighbor are of similar magnitude. (In the worst case, consider a cloud of points distributed on the surface of a sphere centered at the origin. Every point is equidistant from the origin, so a search for the nearest neighbor from the origin would have to iterate through all points on the surface of the sphere to identify the nearest neighbor – which in this case is not even unique.)
To mitigate the potentially significant performance degradation of a ''k''-d tree search in the worst case, a maximum distance parameter can be provided to the tree search algorithm, and the recursive search can be pruned whenever the closest point in a given branch of the tree cannot be closer than this maximum distance. This may result in a nearest neighbor search failing to return a nearest neighbor, which means no points are within this maximum distance from the query point.
Complexity
* Building a static ''k''-d tree from ''n'' points has the following worst-case complexity:
**
O(''n'' log
2 ''n'') if an sort such as
Heapsort
In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the ...
or
Mergesort
In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same ...
is used to find the median at each level of the nascent tree;
**
O(''n'' log ''n'') if an
median of medians
In computer science, the median of medians is an approximate (median) selection algorithm, frequently used to supply a good pivot for an exact selection algorithm, mainly the quickselect, that selects the ''k''th smallest element of an initially u ...
algorithm
[ Chapter 10.] is used to select the median at each level of the nascent tree;
**
O(''kn'' log ''n'') if ''n'' points are presorted in each of ''k'' dimensions using an sort such as
Heapsort
In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the ...
or
Mergesort
In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same ...
prior to building the .
* Inserting a new point into a balanced ''k''-d tree takes time.
* Removing a point from a balanced ''k''-d tree takes time.
* Querying an axis-parallel range in a balanced ''k''-d tree takes time, where ''m'' is the number of the reported points, and ''k'' the dimension of the ''k''-d tree.
* Finding 1 nearest neighbour in a balanced ''k''-d tree with randomly distributed points takes time on average.
Variations
Volumetric objects
Instead of points, a ''k''-d tree can also contain
rectangle
In Euclidean plane geometry, a rectangle is a quadrilateral with four right angles. It can also be defined as: an equiangular quadrilateral, since equiangular means that all of its angles are equal (360°/4 = 90°); or a parallelogram containi ...
s or
hyperrectangle
In geometry, an orthotopeCoxeter, 1973 (also called a hyperrectangle or a box) is the generalization of a rectangle to higher dimensions.
A necessary and sufficient condition is that it is congruent to the Cartesian product of intervals. If all ...
s.
Thus range search becomes the problem of returning all rectangles intersecting the search rectangle. The tree is constructed the usual way with all the rectangles at the leaves. In an
orthogonal range search, the ''opposite'' coordinate is used when comparing against the median. For example, if the current level is split along x
high, we check the x
low coordinate of the search rectangle. If the median is less than the x
low coordinate of the search rectangle, then no rectangle in the left branch can ever intersect with the search rectangle and so can be pruned. Otherwise both branches should be traversed. See also
interval tree In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to f ...
, which is a 1-dimensional special case.
Points only in leaves
It is also possible to define a ''k''-d tree with points stored solely in leaves.
This form of ''k''-d tree allows a variety of split mechanics other than the standard median split. The midpoint splitting rule
[S. Maneewongvatana and D. M. Mount]
It's okay to be skinny, if your friends are fat
4th Annual CGC Workshop on Computational Geometry, 1999. selects on the middle of the longest axis of the space being searched, regardless of the distribution of points. This guarantees that the aspect ratio will be at most 2:1, but the depth is dependent on the distribution of points. A variation, called sliding-midpoint, only splits on the middle if there are points on both sides of the split. Otherwise, it splits on point nearest to the middle. Maneewongvatana and Mount show that this offers "good enough" performance on common data sets.
Using sliding-midpoint, an
approximate nearest neighbour query can be answered in
.
Approximate range counting can be answered in
with this method.
See also
Close variations:
*
implicit ''k''-d tree, a ''k''-d tree defined by an implicit splitting function rather than an explicitly-stored set of splits
*
min/max ''k''-d tree, a ''k''-d tree that associates a minimum and maximum value with each of its nodes
*
Relaxed ''k''-d tree, a ''k''-d tree such that the discriminants in each node are arbitrary
Related variations:
*
Quadtree
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four ...
, a space-partitioning structure that splits in two dimensions simultaneously, so that each node has 4 children
*
Octree
An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three-dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional ana ...
, a space-partitioning structure that splits in three dimensions simultaneously, so that each node has 8 children
*
Ball tree, a multi-dimensional space partitioning useful for nearest neighbor search
*
R-tree and
bounding interval hierarchy A bounding interval hierarchy (BIH) is a partitioning data structure similar to that of bounding volume hierarchies or kd-trees. Bounding interval hierarchies can be used in high performance (or real-time) ray tracing and may be especially useful ...
, structure for partitioning objects rather than points, with overlapping regions
*
Vantage-point tree A vantage-point tree (or VP tree) is a metric tree that segregates data in a metric space by choosing a position in the space (the "vantage point") and partitioning the data points into two parts: those points that are nearer to the vantage point th ...
, a variant of a ''k''-d tree that uses hyperspheres instead of hyperplanes to partition the data
Problems that can be addressed with ''k''-d trees:
*
Recursive partitioning Recursive partitioning is a statistical method for multivariable analysis. Recursive partitioning creates a decision tree that strives to correctly classify members of the population by splitting it into sub-populations based on several dichotomous ...
, a technique for constructing statistical decision trees that are similar to ''k''-d trees
*
Klee's measure problem
In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of ( multidimensional) rectangular ranges can be computed. Here, a ''d''-dimensional rectangular range is defined to be a Cart ...
, a problem of computing the area of a union of rectangles, solvable using ''k''-d trees
*
Guillotine problem
Guillotine cutting is the process of producing small rectangular items of fixed dimensions from a given large rectangular sheet, using only guillotine-cuts. A guillotine-cut (also called an edge-to-edge cut) is a straight bisecting line going from ...
, a problem of finding a ''k''-d tree whose cells are large enough to contain a given set of rectangles
Open source implementations
*
ALGLIB
ALGLIB is a cross-platform open source numerical analysis and data processing library. It can be used from several programming languages (C++, C#, VB.NET, Python, Delphi).
ALGLIB started in 1999 and has a long history of steady development with r ...
has
C# and
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
implementations of ''k''-d tree based nearest neighbor and approximate nearest neighbor algorithms
*
CGAL the Computational Algorihms Library, has an implementations of ''k''-d tree based nearest neighbor, approximate nearest neighbor as well as range search algorithms.
*
SciPy
SciPy (pronounced "sigh pie") is a free and open-source Python library used for scientific computing and technical computing.
SciPy contains modules for optimization, linear algebra, integration, interpolation, special functions, FFT, signal ...
, a Python library for scientific computing, contains implementations of ''k''-d tree based nearest neighbor lookup algorithms.
*
scikit-learn
scikit-learn (formerly scikits.learn and also known as sklearn) is a free software machine learning library for the Python programming language.
It features various classification, regression and clustering algorithms including support-vector ...
, a Python library for machine learning, contains implementations of ''k''-d trees to back nearest neighbor and radius neighbors searches.
References
{{DEFAULTSORT:K-d tree
Computer graphics data structures
Trees (data structures)
Geometric data structures
Database index techniques
Data types
Articles with example Python (programming language) code