# Nearest neighbor search in a multidimensional space

### Description

Finds a user specified number of nearest neighbors of a multivariate space defined by the coordinates of the input matrix. Alternatively, the user can specify a maximum distance over which to search for nearest neighbors.

### Usage

1 2 | ```
findNeighbors(x, n.neighbor=NULL, metric=1, max.distance = 0.,
olag=0, sort.distances=TRUE)
``` |

### Arguments

`x` |
an embedding matrix. Each column of the matrix respresents a single coordinate of the embedding and each row denotes the coordinates of a single point in the embedding. |

`max.distance` |
used an alternative to |

`metric` |
the metric used to define the distance between
points in the embedding. Choices are limited to |

`n.neighbor` |
the number of neighbors to find for each point in
the embedding. If not |

`olag` |
an integer scalar representing the orbital lag, which defines the
number of points along a trajectory (both forwards and backwards) that are to be excluded
as nearest neighbor candidates. This argument helps to prevent temporally correlated data samples
from being considered as neighbors to a given point in the embedding. This sitatuation can
arise, for example, when a smooth trajectory has been highly oversampled in time. An orbital lag of 0
implies that the reference point itself may be considered a neighbor candidate. To exclude self-neighbors,
set |

`sort.distances` |
a logical flag. If |

### Details

An efficient recursive algorithm is used to find all nearest neighbors. First a quadtree is developed to form a recursive partitioning of the embedding matrix, returning row and column index vectors and a list of medians which may be used to sort the embedding matrix. The quadtree is then traversed as an efficient means to find nearest neighbors.

### Value

a list containing the indices of the original points
(corresponding to rows of the embedding
matrix), the indices of the neighbors found, and the distance
between them. The distance metric is based on that specified
by the optional `metric`

input argument.

### References

Friedman, J., Bentley, J. L., and Finkel, R. A.,
“An algorithm for finding best matches in logarithmic expected time",
*ACM Transactions on Mathematical Software* **3**, 209–226, 1977.

### See Also

`FNN`

, `FNS`

.

### Examples

1 2 3 4 5 6 7 8 9 10 11 12 | ```
## Calculate the 10 nearest neighbors for each
## point of 3-dimensional delayed coordinate
## embedding of the beamchaos data. Exclude
## self-neighbors from the output.
embedding <- embedSeries( beamchaos, dim = 3, tlag = 10 )
nn <- findNeighbors( embedding, n.neighbor=10, olag=1 )
## Using the same data, find only those neighbors
## within a distance 0.1 of the original points
## based on an L-infinity metric
nn.dist <- findNeighbors( embedding, max.distance=0.1,
metric=Inf, olag=1 )
``` |