findNN {protViz}

find index of nearest neighbor

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 \le k \le n and k is not o so that

abs(vec[k] - q[i]) < abs(vec[o] - q[i]).

Usage

    findNN(q, vec, check) 
    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_2(n)) time complexity where n is defined as length(vec) and m is length(m).

findNN is implemented using C library function - bsearch(), while findNN_ uses C++11 STL function lower_bound().

Author(s)

Christian Panse 2007, 2008, 2009, 2010, 2012 , 2015 based on the C++ STL lower_bound method.

References

• https://cplusplus.com/reference/algorithm/lower_bound/

See Also

findInterval

Examples

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