# 376.kdtree

SPEC Benchmark Description File

## Benchmark Name

376.kdtree

## Benchmark Author

R. Brown

## Benchmark Program General Category

Sorting and Searching

## Benchmark Description

The program builds a k-d tree using random coordinate points,
then searches the k-d tree for points that are proximate to each
point in the tree.

The build phase is single threaded, but the search phase is
multi-threaded using the OpenMP task directive.

The points that are sorted into the tree are defined using a random
number gener ator to generate either 3D (x,y,z) or 4D (x,y,z,w) points
that are stored one large 2 D array, xyzw. In order to build the k-d
tree, four index arrays xi, yi, zi and wi are created then heap-sorted
using the x, y, z and w coordinate data from the xy zw array. The k-d
tree is a balanced tree, and is built in O[n*log(n)] time.

Once the k-d tree is built, the k-d tree is walked to visit each point,
and that point is used as a query point to search the k-d tree for all
other points that lie within a specific radius of that query point.
The default value for that radius is one-tenth the range of the random
numbers. The total number of points found by using each point
successively as a query point, as well as the total execution time, are
reported. Note that the walking and searching of the k-d tree imply
two recursive traversals of the k-d tree.

## Input Description

Input parameters

- n = 100000 (default), the number of points to generate
- cutoffdivisor = 10 (default), the number by which to divide the
range of random numbers to obtain the radius to search
- maxdepth = 2 (default), the number of levels from the root of the
k-d tree where the OpenMP task directive will immediately execute
the child task that it creates, instead of adding that child task to
a queue

## Output Description

The program returns the number of points found to meet the
input criteria.

## Programming Language

C++

## Known portability issues

None

## Reference

Last update: 24 February 2012