classPiiKdTree
#include <PiiKdTree.h>
K-dimensional tree.
Description
The kd-tree is a binary tree in which every node is a k-dimensional point. Each non-leaf node in the tree splits the k-dimensional hyperspace with a hyperplane that is aligned to one of the axes and passes through the point in the node.
The kd-tree can be used to quickly look up nearest neighbors in
large databases. For randomly distributed data, the complexity of
the algorithm is O(log N), which is much better than
the O(N) of exhaustive search. The advantage however
quickly diminishes with growing feature space dimensionality. As a
general rule, exact NN search using the kd-tree is
advantageous if and only if
,
where N is the number of samples and k is the feature space
dimensionality.
PiiKdTree includes a variant of the basic NN look-up algorithm that performs approximate NN search. (k-NN search is also supported.) Instead of recursively checking all possible branches of the tree the approximate algorithm orders the look-ups so that the most likely ones come first. The algorithm stops when the exact nearest neighbor has been found or a predefined maximum number of look-ups have been performed. This makes it possible to set a hard upper bound for the search time while still returning the nearest neighbor(s) with a high probability.
PiiKdTree only works with geometric distances. Thus, there is no option to use user-defined distance measures. If you need a special distance measure, exhaustive search is currently the only viable option.
Public types
|
typedef PiiSampleSet::Traits< SampleSet
>::ConstFeatureIterator
|
Constructors and destructor
|
(
Constructs a kd-tree out of the given model samples. |
|
|
Constructs a deep copy of another kd-tree. |
|
|
( )
Constructs an empty kd-tree. |
|
|
( )
Destroys the kd-tree. |
Public member functions
|
void
|
Deletes the old kd-tree (if any) and rebuilds a new one based on the given model samples. |
|
int
|
(
Returns the index of a probably nearest neighbor in the model set. |
|
int
|
(
Returns the index of the nearest neighbor in the model set. |
|
(
Returns the n closest matches of sample. |
|
|
(
Returns n matches that are probably the closest of sample. |
|
|
SampleSet
|
( )
Returns the model sample set that was used to construct the kd-tree. |
|
Assigns other to |
|
|
template<class Stream>
void
|
(
Prints the structure of the k-d tree to stream. |
Friends
|
friend struct
|
|
Function details
-
PiiKdTree
(- const SampleSet & modelSet
Constructs a kd-tree out of the given model samples.
-
PiiKdTree
Constructs a deep copy of another kd-tree.
-
PiiKdTree
()Constructs an empty kd-tree.
-
~PiiKdTree
()Destroys the kd-tree.
-
template<class Archive>
void serialize
(- Archive & archive
- const unsigned int
[inline] -
void buildTree
Deletes the old kd-tree (if any) and rebuilds a new one based on the given model samples.
Parameters
- modelSet
-
model samples
- controller
-
an optional external controller that can be used to stop building the tree on user request.
Exceptions
- PiiClassificationException&
-
if the algorithm was interrupted.
-
int findClosestMatch
(- Sample sample
- int maxEvaluations
- double * distance = 0
Returns the index of a probably nearest neighbor in the model set.
This version of the look-up algorithm may not return the exact nearest neighbor, but it does so with a high probability. Approximate NN search is useful in high-dimensional spaces where the exact algorithm may be slower than exhaustive search.
Parameters
- sample
-
input feature vector
- maxEvaluations
-
the maximum number of node look-ups to be done. If you set this value to
log(N), the algorithm will do a simple best first search to the first leaf node. Usually, it is a good idea to give the algorithm a bit more time to find a good match. If you set this value to the size of the model set, the exact nearest neighbor will be returned. - distance
-
an optional output-value argument that will store the squared geometric distance to the closest neighbor of sample.
Returns
the index of the closest sample in the model set, or -1 if the set is empty.
-
int findClosestMatch
(- Sample sample
- double * distance = 0
Returns the index of the nearest neighbor in the model set.
Parameters
- sample
-
input feature vector
- distance
-
an optional output-value argument that will store the squared geometric distance to the closest neighbor of sample.
Returns
the index of the closest sample in the model set, or -1 if the set is empty.
-
PiiClassification::MatchList findClosestMatches
(- Sample sample
- int n
Returns the n closest matches of sample.
This function is equivalent to PiiClassification::findClosestMatches(). It returns an exact answer and may not perform well in high-dimensional spaces.
Returns
the n closest matches. Note that if the model data set is smaller than n, less than n matches may be returned.
-
PiiClassification::MatchList findClosestMatches
(- Sample sample
- int n
- int maxEvaluations
Returns n matches that are probably the closest of sample.
This function stops after maxEvaluations most probable nodes have been checked and may not return the exact nearest neighbors.
Parameters
- sample
-
input feature vector
- n
-
the number of closest matches to return.
- maxEvaluations
-
the maximum number of node look-ups to be done. A suitable value is about n *
log(N), where N is the number of samples in the model set.
Returns
the n closest matches. Note that if either the model data set or maxEvaluations is smaller than n, less than n matches may be returned.
-
SampleSet modelSet
()[inline]Returns the model sample set that was used to construct the kd-tree.
-
Assigns other to
this. -
template<class Stream>
void print
(- Stream & stream
[inline]Prints the structure of the k-d tree to stream.
This function is mainly for informational and debugging purposes.
Add a note
Not a single note added yet. Be the first, add yours.