| nn2 {RANN} | R Documentation |
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 |
A data frame or matrix where each row is a point. |
query |
A set of points that will be queried against data - must have same number of columns. If missing, uses data. |
k |
The maximum number of near neighbours to compute. The default value is set to 10. |
treetype |
Either 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 |
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.
A list of length 2 with elements, nn.idx and nn.dists
nn.idx |
A MxP data.frame returning the near neighbour indexes. |
nn.dists |
A MxP data.frame returning the near neighbour Euclidean distances. |
Gregory Jefferis based on earlier code by Samuel E. Kemp (knnFinder package)
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.
x1 <- runif(100, 0, 2*pi) x2 <- runif(100, 0,3) DATA <- data.frame(x1, x2) nearest <- nn2(DATA,DATA)