Into

Modules

Documentation

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

(
  • const SampleSet & modelSet
)

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
(
  • Sample sample
  • int maxEvaluations
  • double * distance = 0
)

Returns the index of a probably nearest neighbor in the model set.

int
(
  • Sample sample
  • double * distance = 0
)

Returns the index of the nearest neighbor in the model set.

(
  • Sample sample
  • int n
)

Returns the n closest matches of sample.

(
  • Sample sample
  • int n
  • int maxEvaluations
)

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 this.

template<class Stream>
void
(
  • Stream & stream
)

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.

  • PiiKdTree & operator=

    ( )

    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.

Notes (0)

Add a note

Not a single note added yet. Be the first, add yours.