Problem Based Benchmark Suite (2020)

K-Nearest Neighbors (KNN):

Given points in 2 and 3 dimensions find the k nearest neighbors for each point.

Input and Output File Formats

The input needs to be in either the 2d or 3d points file format. The output needs to be in the sequence file format and must contain for each point the integer index of each of its closest k neighbors sorted by distance (nearest first). For n input points, the number of integers in the output is threfore k × n. The neighbors of each point are adjacent and the points must be in the same order as the input.

Default Input Distributions

Each distribution should be run for n=10,000,000. The weights used for average time are given in parentheses (all weights are equal).

• (1) For k = 1, 2 dimensional points selected at random uniformly distributed in a cube.

  uniform -d 2 <n> <filename>

• (1) For k = 1, 2 dimensional points selected at random from the Kuzmin distribution.

  plummer -d 2 <n> <filename>

• (1) For k = 1, 3 dimensional points selected at random from the Kuzmin distribution.

  uniform -d 3 <n> <filename>

• (1) For k = 1, 3 dimensional points selected at random on the surface of a sphere.

  uniform -S -d 3 <n> <filename>

• (1) For k = 10, 3 dimensional points selected uniformly at random in a cube.

  uniform -d 3 <n> <filename>

• (1) For k = 10, 3 dimensional points selected randomly from the Plummer distribution.

  plummer -d 3 <n> <filename>