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
SearchTree *	nn_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.