bufferkdtree (C sources)
C source code for the Python bufferkdtree implementation
|
#include "include/kdtree.h"
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) |
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).
*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
*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)
*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.
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)
*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.
*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)
*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.
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.
*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".
*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 |