Uses a kd-tree to find the p number of near neighbours for each point in an input/output dataset. The advantage of the kd-tree is that it runs in O(M log M) time.

```
nn2(data, query = data, k = min(10, nrow(data)), treetype = c("kd", "bd"),
searchtype = c("standard", "priority", "radius"), radius = 0, eps = 0)
```

data

An **M** x **d** data.frame or matrix, where each of the
**M** rows is a point or a (column) vector (where **d=1**).

query

A set of **N** x **d** points that will be queried against
`data`

. **d**, the number of columns, must be the same as
`data`

. If missing, defaults to `data`

.

k

The maximum number of nearest neighbours to compute. The default value is set to the smaller of the number of columnns in data

treetype

Character vector specifying the standard `'kd'`

tree or a
`'bd'`

(box-decomposition, AMNSW98) tree which may perform better for
larger point sets

searchtype

See details

radius

Radius of search for searchtype='radius'

eps

Error bound: default of 0.0 implies exact nearest neighbour search

A `list`

of length 2 with elements:

A **N** x **k** integer `matrix`

returning the near
neighbour indices.

A **N** x **k** `matrix`

returning the near
neighbour Euclidean distances.

The `RANN`

package utilizes the Approximate Near Neighbor (ANN) C++
library, which can give the exact near neighbours or (as the name suggests)
approximate near neighbours to within a specified error bound. For more
information on the ANN library please visit
http://www.cs.umd.edu/~mount/ANN/.

Search types: `priority`

visits cells in increasing order of distance
from the query point, and hence, should converge more rapidly on the true
nearest neighbour, but standard is usually faster for exact searches.
`radius`

only searches for neighbours within a specified radius of the
point. If there are no neighbours then nn.idx will contain 0 and nn.dists
will contain 1.340781e+154 for that point.

Bentley J. L. (1975), Multidimensional binary search trees used for associative search. Communication ACM, 18:309-517.

Arya S. and Mount D. M. (1993), Approximate nearest neighbor searching, Proc. 4th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA'93), 271-280.

Arya S., Mount D. M., Netanyahu N. S., Silverman R. and Wu A. Y (1998), An optimal algorithm for approximate nearest neighbor searching, Journal of the ACM, 45, 891-923.

```
# NOT RUN {
x1 <- runif(100, 0, 2*pi)
x2 <- runif(100, 0,3)
DATA <- data.frame(x1, x2)
nearest <- nn2(DATA,DATA)
# }
```

Run the code above in your browser using DataLab