tdkdtree.c File Reference

A kd-tree data structure for top-down searching: source file. More...

#include "tdkdtree.h"
#include "queue.h"
#include <stdio.h>
#include <stdlib.h>

Include dependency graph for tdkdtree.c:

This graph shows which files directly or indirectly include this file:

Functions
static void	globaltreebuild ()
static infokdnode *	infokdnodebuild ()
static kdtree *	localtreebuild ()
static kdnode *	tdbuild ()
static kdnode *	tdfindcutvalues ()
static int	arrange ()
static void	rnn ()
static double	distsqrd2 ()
static void	destroytdkdtreenode ()
kdtree *	newtdkdtree (double **param_y, int param_n, int param_k, int p, int q)
	Initialization for the tree building.
static void	globaltreebuild (int p)
	Building first log(p) levels of a tree.
static infokdnode *	infokdnodebuild (int l, int u)
	Building a `infokdnode` data structure.
static kdtree *	localtreebuild (kdtree *tree, int p, int q)
	Building a local tree.
static kdnode *	tdbuild (int l, int u)
	Recursive building for a tree.
static kdnode *	tdfindcutvalues (int l, int u, kdnode *p)
	Computing the dimension with the maximal spread and an estimation of the median value in that dimension.
static int	arrange (int l, int u, double cutval, int cutdim)
	Arranging the permutation vector.
int	tdnn (int j, double *param_nndist2)
	Computing the nearest neighbor for a given point.
static void	rnn (kdnode *p)
	Recursive searching for the nearest neighbor.
static double	distsqrd2 (int i, int j)
	Computing the square of the Euclidean distance between two points.
void	destroytdkdtree (kdtree *tree)
	Destroying a kd-tree.
static void	destroytdkdtreenode (kdnode *node)
	Recursive destruction for all the internal nodes in a kd-tree.
Variables
static double **	y = NULL
	Set of n points in k dimensions.
static int	n = 0
	Total number of points in the tree.
static int	k = 0
	Number of dimensions of the tree.
static int *	perm = NULL
	Global permutation vector (aka big bucket).
static kdnode *	root = NULL
	Root of the tree.
static int	cutoff = 15
	Maximum number of points allowed in a bucket. If the number of repeated points is greater than this then the value is ignored.
static int	bigbucket = 0
	In the tree building, this flag contains the state of the last call to the function `findmedian`. If the value is 1 then was detected a number of equal points greater than `cutoff` (the maximum number of elements in a bucket).
static int	nntarget = 0
	In a searching for the nearest neighbor, this global variable contains the index of the target point.
static int	nnfound = 0
	In a searching for the nearest neighbor, this global variable saves the last index founded.
static double	nndist2 = 0.0
	In a searching for the nearest neighbor, this global variable saves the square of the last distance computed.

Detailed Description

A kd-tree data structure for top-down searching: source file.

Version:: 10.10

Author:: Julio José Águila Guerrero

Date:: October 22nd, 2010

A straightforward implementation of a kd-tree data structure for top-down searching based on a description of J. L. Bentley (1990).

Note:: Last change was in October 22nd, 2010.

Definition in file tdkdtree.c.

Function Documentation

static int arrange	(	int	l,
		int	u,
		double	cutval,
		int	cutdim
	)			`[static]`

Arranging the permutation vector.

Permuting perm[l,u] such that perm[m] contains a point that is not greater in the dimension cutdim that any point to its left, and is similarly not less than the points to its right.
Additionaly, the function computes if the number of repeated points is greater than cutoff (the maximum number of elements in a bucket).

Parameters:

	l	Lower bound in `perm`.
	u	Larger bound in `perm`.
	cutval	Cut value considered in the arranging.
	cutdim	Cut dimension considered in the arranging.

Returns:: None.

Definition at line 375 of file tdkdtree.c.

static int arrange ( ) [static]

See also:: arrange

Here is the caller graph for this function:

void destroytdkdtree ( kdtree * tree )

Destroying a kd-tree.

The dynamic memory is released and the global static variables are cleaned. The recursive function destroykdtreenode releases the memory allocated for all the internal nodes.

Parameters:

tree

A kd-tree data structure.

Returns:: None.

Definition at line 554 of file tdkdtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

static void destroytdkdtreenode ( kdnode * node ) [static]

Recursive destruction for all the internal nodes in a kd-tree.

In the first invocation the parameter node is the root of the tree. All the internal nodes are released in a recursive manner.

Parameters:

node

A kd-tree node data structure.

Returns:: None.

Definition at line 583 of file tdkdtree.c.

Here is the call graph for this function:

static void destroytdkdtreenode ( ) [static]

See also:: destroytdkdtreenode

Here is the caller graph for this function:

static double distsqrd2	(	int	i,
		int	j
	)			`[static]`

Computing the square of the Euclidean distance between two points.

Parameters:

	i	Index of the first point.
	j	Index of the second point.

Returns:: The square of the Euclidean distance between y(i) and y(j).

Definition at line 524 of file tdkdtree.c.

static double distsqrd2 ( ) [static]

See also:: distsqrd2

Here is the caller graph for this function:

static void globaltreebuild ( int p ) [static]

Building first log(p) levels of a tree.

The tree build is a virtually construction when the information is storing in a queue.

Parameters:

p

Number of processes.

Returns:: None.

Definition at line 129 of file tdkdtree.c.

Here is the call graph for this function:

static void globaltreebuild ( ) [static]

See also:: globaltreebuild

Here is the caller graph for this function:

static infokdnode* infokdnodebuild	(	int	l,
		int	u
	)			`[static]`

Building a infokdnode data structure.

The node created containing information about the cut dimension, the cut value, and the bounds for the loson and hison subtrees.

Parameters:

	l	Lower bound in `perm`.
	u	Larger bound in `perm`.

Returns:: The information that represents a internal node in the tree between the bounds perm[l,u]</tt.

Definition at line 170 of file tdkdtree.c.

Here is the call graph for this function:

static infokdnode* infokdnodebuild ( ) [static]

See also:: infokdnodebuild

Here is the caller graph for this function:

static kdtree* localtreebuild	(	kdtree *	tree,
		int	p,
		int	q
	)			`[static]`

Building a local tree.

The local tree build function uses a kdtree data structure previously initialized.

Parameters:

	tree	A `kdtree` data structure peviously initialized.
	p	Number of processes.
	q	Identifier of the local process.

Returns:: A kd-tree that has a root in the qth internal node of the level log(p).

Definition at line 207 of file tdkdtree.c.

Here is the call graph for this function:

static kdtree* localtreebuild ( ) [static]

See also:: localtreebuild

Here is the caller graph for this function:

kdtree* newtdkdtree	(	double **	param_y,
		int	param_n,
		int	param_k,
		int	p,
		int	q
	)

Initialization for the tree building.

The new data structure and the global static variables are initialized with the appropriate values. The recursive function tdbuild does the work.

Parameters:

	param_y	A set of n points in k-dimensions.
	param_n	Number of points (length of `y`).
	param_k	Number of dimensions for each point (width of `y`).
	p	Number of processes.
	q	Identifier of the local process.

Returns:: A kd-tree that has a root in the qth internal node of the level log(p).

Definition at line 89 of file tdkdtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

static void rnn ( kdnode * p ) [static]

Recursive searching for the nearest neighbor.

At a bucket node, rnn performs a sequential nearest neighbor search. At an internal node, the search first procceds down the closer son, and then searches the farther son only if neccesary. For the common case of the Euclidean metric, Sproull (1988) observes that one need not compute the (expensive) true distance to the nearest neighbor. Computing only the square of the distance is clearly sufficient within a bucket.
The index of the nearest neighbor founded is saved in nnfound and the square of the distance is saved in nndist2.

Parameters:

p

Any node in the tree.

Returns:: None.

Definition at line 473 of file tdkdtree.c.

Here is the call graph for this function:

static void rnn ( ) [static]

See also:: rnn

Here is the caller graph for this function:

static kdnode* tdbuild	(	int	l,
		int	u
	)			`[static]`

Recursive building for a tree.

A new node is created in each calling. If the number of points in perm[l,u] is less than or equal to cutoff the function return a bucket with them. If not, A cut dimension and a cut value are selected using tdfindcutvalues. The function arrange put in position the indexes into perm using that values. A new internal node is created with these values and the sons are created with recursive calls to tdbuild.
If the number of equal points is greater than the cutoff value then a bucket is created ignoring that value.

Parameters:

	l	Lower bound in `perm`.
	u	Larger bound in `perm`.

Returns:: A node that can be a bucket or an internal node. This node is the root of the tree for all the points in perm[l,u]</tt.

Definition at line 265 of file tdkdtree.c.

Here is the call graph for this function:

static kdnode* tdbuild ( ) [static]

See also:: tdbuild

Here is the caller graph for this function:

static kdnode* tdfindcutvalues	(	int	l,
		int	u,
		kdnode *	p
	)			`[static]`

Computing the dimension with the maximal spread and an estimation of the median value in that dimension.

Parameters:

	l	Lower bound in `perm`.
	u	Larger bound in `perm`.
	p	A pointer to a `kdnode` data structure.

Returns:: A pointer to a kdnode data structure that contains the dimension with largest deviation and the median in that dimension using the first thousand values from perm[l,u].

Definition at line 315 of file tdkdtree.c.

static kdnode* tdfindcutvalues ( ) [static]

See also:: tdfindcutvalues

Here is the caller graph for this function:

int tdnn	(	int	j,
		double *	param_nndist2
	)

Computing the nearest neighbor for a given point.

The global static variables are initialized with the appropriate values. The recursive function rnn does the work.

Parameters:

	j	Index of the target point.
	param_nndist2	Output variable which represents the normalized distance between points.

Returns:: The nearest neighbor of the target point j. The normalized distance is returned using the parameter param_nndist2.

Definition at line 442 of file tdkdtree.c.

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

int bigbucket = 0 [static]

In the tree building, this flag contains the state of the last call to the function findmedian. If the value is 1 then was detected a number of equal points greater than cutoff (the maximum number of elements in a bucket).

Definition at line 70 of file tdkdtree.c.

int cutoff = 15 [static]

Maximum number of points allowed in a bucket. If the number of repeated points is greater than this then the value is ignored.

Definition at line 62 of file tdkdtree.c.

int k = 0 [static]

Number of dimensions of the tree.

Definition at line 46 of file tdkdtree.c.

int n = 0 [static]

Total number of points in the tree.

Definition at line 41 of file tdkdtree.c.

double nndist2 = 0.0 [static]

In a searching for the nearest neighbor, this global variable saves the square of the last distance computed.

Definition at line 425 of file tdkdtree.c.

int nnfound = 0 [static]

In a searching for the nearest neighbor, this global variable saves the last index founded.

Definition at line 420 of file tdkdtree.c.

int nntarget = 0 [static]

In a searching for the nearest neighbor, this global variable contains the index of the target point.

Definition at line 415 of file tdkdtree.c.

int* perm = NULL [static]

Global permutation vector (aka big bucket).

Definition at line 51 of file tdkdtree.c.

kdnode* root = NULL [static]

Root of the tree.

Definition at line 56 of file tdkdtree.c.

double** y = NULL [static]

Set of n points in k dimensions.

Definition at line 36 of file tdkdtree.c.

tdkdtree.c File Reference

Functions

Variables

Detailed Description

Function Documentation

Variable Documentation