Functions

src/nnsearch.c File Reference

#include "nnsearch.h"
#include <gsl/gsl_sort.h>
#include "pqueue.h"
#include "mathadd.h"

Go to the source code of this file.

Functions

SearchTreenn_prepare (const double **X, int N, int m, OptArgList *optargs)
void nn_search_k (const SearchTree *S, const double *x, int k, int *nn_idx, double *nn_dist)
void nn_search_k_slow (const double **X, int N, int m, const double *x, int k, int *nn_idx, double *nn_dist, OptArgList *optargs)

Function Documentation

SearchTree* nn_prepare ( const double **  X,
int  N,
int  m,
OptArgList optargs 
)

Initialize the search tree for fast-nearest-neighbour searching.

Parameters:
data matrix of m variables with N measurements each
m dimensionality
N number of measurements
optargs may contain:

  • 'metric=void*' the distance metric used (default=euclidean)
  • 'max_numel_terminal_node=int' the maximum number of elements in a terminal node (default=50)
  • optional arguments for the called function (e.g. metric)
Returns:
the searchtree-struct used to look for nearest neighbours

Definition at line 38 of file nnsearch.c.

void nn_search_k ( const SearchTree S,
const double *  x,
int  k,
int *  nn_idx,
double *  nn_dist 
)

Searching the k nearest neighbour of vector x in searchtree. This implementation uses a searchtree-based method.

Parameters:
S the searchtree, previously initialized by nn_prepare
x query point; must be of dimension m in searchtree S
k number of neighbours to look for
nn_idx memory for holding the indices for the k NN's
nn_dist memory for holding distances for k NN's

Definition at line 147 of file nnsearch.c.

void nn_search_k_slow ( const double **  X,
int  N,
int  m,
const double *  x,
int  k,
int *  nn_idx,
double *  nn_dist,
OptArgList optargs 
)

Searching the k nearest neighbour of vector x in X. This is a slow implementation:

  • calculate all distances from x to any point in X
  • sort the distances
  • return the indices with the k smallest distances
Parameters:
X dataset to query
N,m dimensions of X
x query point; must be of dimension m
k number of neighbours to look for
nn_idx memory for holding the indices for the k NN's
nn_dist memory for holding distances for k NN's
optargs may contain:

  • 'metric=void*' the distance metric used (default=euclidean)
  • optional arguments for the called function (e.g. metric)

Definition at line 102 of file nnsearch.c.