kdtree.c File Reference

#include "include/kdtree.h"

Include dependency graph for kdtree.c:

Functions
void	kd_tree_init_tree_record (KD_TREE_RECORD *record, int kd_tree_depth, FLOAT_TYPE *Xtrain, int nXtrain, int dXtrain)
void	kd_tree_free_tree_record (KD_TREE_RECORD *record)
void	kd_tree_build_tree (KD_TREE_RECORD *kdtree_record, KD_TREE_PARAMETERS *params)
void	kd_tree_build_recursive (KD_TREE_RECORD *kdtree_record, KD_TREE_PARAMETERS *params, int left, int right, int idx, int depth)
void	kd_tree_query_tree_sequential (FLOAT_TYPE *test_pattern, FLOAT_TYPE *d_min, int *idx_min, int K, KD_TREE_RECORD *record)
void	kd_tree_brute_force_leaf (void *XI, int dim, int fr_idx, int to_idx, FLOAT_TYPE *test_pattern, FLOAT_TYPE *d_min, int *idx_min, int K)
int	kd_tree_find_best_split (int depth, int left, int right, KD_TREE_RECORD *kdtree_record, KD_TREE_PARAMETERS *params)
void	kd_tree_generate_training_patterns_indices (KD_TREE_RECORD *kdtree_record)
int	kd_tree_split_training_patterns_via_pivot (void *XI, int left, int right, int axis, int dim)
void	kd_tree_insert (FLOAT_TYPE pattern_dist, int pattern_idx, FLOAT_TYPE *nearest_dist, int *nearest_idx, int K)

Function Documentation

void kd_tree_brute_force_leaf	(	void *	XI,
		int	dim,
		int	fr_idx,
		int	to_idx,
		FLOAT_TYPE *	test_pattern,
		FLOAT_TYPE *	d_min,
		int *	idx_min,
		int	K
	)

Brute-force nearest neigbhor search in a leaf of the tree (determined by fr_idx, to_idx, and XI).

Parameters

*XI	Pointer to array containing the patterns and the associated original training indices
dim	Dimensionality of the patterns
fr_idx	The from index in the array (left bound)
to_idx	The to index in the array (right bound)
*test_pattern	Pointer to test pattern
*d_min	Pointer to array that shall contain the distances afterwards
*idx_min	Pointer to array that shall contain the indices afterwards
K	Number of nearest neighbors

void kd_tree_build_recursive	(	KD_TREE_RECORD *	kdtree_record,
		KD_TREE_PARAMETERS *	params,
		int	left,
		int	right,
		int	idx,
		int	depth
	)

Function to recursively build a kd tree

Parameters

*record	A kd tree record instance
*params	Associated kd tree parameters
left	left bound for training patterns
right	right bound for training patterns
idx	Node index
depth	Current tree depth

void kd_tree_build_tree	(	KD_TREE_RECORD *	kdtree_record,
		KD_TREE_PARAMETERS *	params
	)

Builds the kd-tree (recursive construction)

Parameters

*record	A kd tree record instance
*params	Associated kd tree parameters

int kd_tree_find_best_split	(	int	depth,
		int	left,
		int	right,
		KD_TREE_RECORD *	kdtree_record,
		KD_TREE_PARAMETERS *	params
	)

Finds the splitting axis.

Parameters

depth	The current tree depth
left	The left bound
right	The right bound
*kdtree_record	Record storing the tree instances
*params	Struct containing the parameters

void kd_tree_free_tree_record

(

KD_TREE_RECORD *

record

)

Frees space for the kd tree (e.g., nodes and leaves)

Parameters

*record

A kd tree record instance

void kd_tree_generate_training_patterns_indices

(

KD_TREE_RECORD *

kdtree_record

)

Parse patterns and store the original indices (this array of both the FLOAT_TYPEs and the indices) is sorted in-place during the construction of the kd-tree.

Parameters

*kdtree_record

Record storing the tree instances

void kd_tree_init_tree_record	(	KD_TREE_RECORD *	record,
		int	kd_tree_depth,
		FLOAT_TYPE *	Xtrain,
		int	nXtrain,
		int	dXtrain
	)

Initializes space for the kd tree (e.g., nodes and leaves)

Parameters

*record	The kd tree struct instance
kd_tree_depth	The desired tree depth
*Xtrain	Pointer to array containing the patterns (as FLOAT_TYPE)
nXtrain	Number of patterns
nXtrain	Dimensionality of each pattern

void kd_tree_insert	(	FLOAT_TYPE	pattern_dist,
		int	pattern_idx,
		FLOAT_TYPE *	nearest_dist,
		int *	nearest_idx,
		int	K
	)

Inserts the value pattern_dist with index pattern_idx in the list nearest_dist of FLOAT_TYPEs and the list nearest_idx of indices. Both lists contain at most K elements.

Parameters

pattern_dist	Distance to the (current) pattern
pattern_idx	The index of the (current) pattern
*nearest_dist	The array of floats to be updated
*nearest_idx	The array of indices to be updated
K	The number of nearest neighbors

void kd_tree_query_tree_sequential	(	FLOAT_TYPE *	test_pattern,
		FLOAT_TYPE *	d_min,
		int *	idx_min,
		int	K,
		KD_TREE_RECORD *	record
	)

Queries the kd-tree to obtain the nearest neigbhors, sequential version.

Parameters

*test_pattern	The test pattern for which the nearest neighbors shall be computed
*d_min	Float array that shall contain the distances
*idx_min	Integer array to store the nearest neighbor indices
K	Number of nearest neigbhors that shall be found
*record	A kd tree record instance

int kd_tree_split_training_patterns_via_pivot	(	void *	XI,
		int	left,
		int	right,
		int	axis,
		int	dim
	)

Sorts the training patterns in range left to right (inclusive) with respect to "axis".

Parameters

*XI	Pointer to array containing the patterns and the associated original training indices
left	Left bound
right	Right bound
axis	The current axis
dim	The dimensionality of the patterns