Problem Based Benchmark Suite

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).
last modified 15:18, 05 Jun 2012

This project has been funded by the following sources:
Intel Labs Academic Research Office for the Parallel Algorithms for Non-Numeric Computing Program,
National Science Foundation, and
IBM Research.