findNN: find index of nearest neighbor

Description Usage Arguments Details Author(s) Examples

View source: R/findNN.R

Description

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]).

Usage

1
    findNN(q, vec, check) 

Arguments

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 vec is sorted. default is FALSE

Details

The internal algorithm of findNN is implemented as binary search. findNN has O(m * log(n)) time complexity.

Author(s)

Christian Panse 2007, 2008, 2009, 2010, 2012 based on the c stdlib bsearch methode and the R package:base function findInterval.

Examples

 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
    (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)

protViz documentation built on Nov. 18, 2017, 4:01 a.m.