# findNN: find index of nearest neighbor In protViz: Visualizing and Analyzing Mass Spectrometry Related Data in Proteomics

## 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.