| findNN {protViz} | R Documentation |
Given a vector of sorted double values vec of size
n and a vector of m query objects q.
findNN determines for each element q[i] in q
the nearest neighbor index o so that the following remains true:
there is no element k with 1 ≤ k
≤ n and k is not o so that
abs(vec[k] - q[i]) < abs(vec[o] - q[i]).
findNN(q, vec, check)
q |
a double vector which can be considered as query objects. |
vec |
a sorted double vector which can be considered as a data base. |
check |
boolean enables test if |
The internal algorithm of findNN is implemented as binary search.
findNN has O(m * log(n)) time complexity.
Christian Panse 2007, 2008, 2009, 2010, 2012 based on the c stdlib bsearch methode and the R package:base function findInterval.
(NNidx <- findNN(q<-c(1, 1.0001, 1.24, 1.26), DB<-seq(1,5,by=0.25)))
(NNidx == c(1,1,2,2))
DB<-sort(rnorm(100, mean=100, sd=10))
# should be 0
unique(DB[findNN(DB,DB)] - DB)
q<-rnorm(100, mean=100)
idx.NN<-findNN(q,DB)
hist(DB[findNN(q,DB)] - q)
# definition of findNN holds
i<-1:5
findNN(3.5, i)
i<-1:6
findNN(3.5, i)
# compare ANSI-C binary search with C++ std::lower_bound
DB<-c(rep(1.0, 3), rep(2.0, 3))
q<-c(-1, 1.0, 1.01, 1.5, 1.9)
abs(DB[findNN(q, DB)] - q)
abs(DB[findNN_(q, DB)] - q)
DB<-sort(rnorm(100, mean=100, sd=10))
# should be 0
unique(DB[findNN_(DB,DB)] - DB)
q<-rnorm(100, mean=100)
idx.NN<-findNN_(q,DB)
hist(DB[findNN_(q,DB)] - q)
# definition of findNN_ holds
i<-1:5
findNN_(3.5, i)
i<-1:6
findNN_(3.5, i)