File: nn2.Rd

package info (click to toggle)
r-cran-rann 2.6.1-1
  • links: PTS, VCS
  • area: main
  • in suites: bookworm, bullseye, sid
  • size: 384 kB
  • sloc: cpp: 2,638; sh: 13; ansic: 12; makefile: 2
file content (82 lines) | stat: -rw-r--r-- 3,015 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/nn.R
\name{nn2}
\alias{nn2}
\title{Nearest Neighbour Search}
\usage{
nn2(data, query = data, k = min(10, nrow(data)), treetype = c("kd",
  "bd"), searchtype = c("standard", "priority", "radius"), radius = 0,
  eps = 0)
}
\arguments{
\item{data}{An \bold{M} x \bold{d} data.frame or matrix, where each of the 
\bold{M} rows is a point or a (column) vector (where \bold{d=1}).}

\item{query}{A set of \bold{N} x \bold{d} points that will be queried against 
\code{data}. \bold{d}, the number of columns, must be the same as 
\code{data}. If missing, defaults to \code{data}.}

\item{k}{The maximum number of nearest neighbours to compute. The default 
value is set to the smaller of the number of columnns in data}

\item{treetype}{Character vector specifying the standard \code{'kd'} tree or a
\code{'bd'} (box-decomposition, AMNSW98) tree which may perform better for 
larger point sets}

\item{searchtype}{See details}

\item{radius}{Radius of search for searchtype='radius'}

\item{eps}{Error bound: default of 0.0 implies exact nearest neighbour search}
}
\value{
A \code{list} of length 2 with elements:
 
 \item{nn.idx}{A \bold{N} x \bold{k} integer \code{matrix} returning the near
 neighbour indices.}
 
 \item{nn.dists}{A \bold{N} x \bold{k} \code{matrix} returning the near 
 neighbour Euclidean distances.}
}
\description{
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.
}
\details{
The \code{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 
\url{http://www.cs.umd.edu/~mount/ANN/}.

Search types: \code{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. 
\code{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.
}
\examples{

x1 <- runif(100, 0, 2*pi)
x2 <- runif(100, 0,3)
DATA <- data.frame(x1, x2)
nearest <- nn2(DATA,DATA)
}
\references{
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.
}
\author{
Gregory Jefferis based on earlier code by Samuel E. Kemp (knnFinder 
 package)
}
\keyword{nonparametric}