# Detecting exact nearest neighbors

Aaron Lun1

1Cancer Research UK Cambridge Institute, Cambridge, United Kingdom

#### Revised: 2 December 2018

#### Package

BiocNeighbors 1.2.0

# 1 Introduction

The BiocNeighbors package implements a few algorithms for exact nearest neighbor searching:

- The k-means for k-nearest neighbors (KMKNN) algorithm (Wang 2012) uses k-means clustering to create an index. Within each cluster, the distance of each of that cluster’s points to the cluster center are computed and used to sort all points. Given a query point, the distance to each cluster center is determined and the triangle inequality is applied to determine which points in each cluster warrant a full distance calculation.
- The vantage point (VP) tree algorithm (Yianilos 1993) involves constructing a tree where each node is located at a data point and is associated with a subset of neighboring points. Each node progressively partitions points into two subsets that are either closer or further to the node than a given threshold. Given a query point, the triangle inequality is applied at each node in the tree to determine if the child nodes warrant searching.

Both methods involve a component of randomness during index construction, though the k-nearest neighbors result is fully deterministic11 Except in the presence of ties, see `?findKNN` for details..

# 2 Identifying k-nearest neighbors

The most obvious application is to perform a k-nearest neighbors search. We’ll mock up an example here with a hypercube of points, for which we want to identify the 10 nearest neighbors for each point.

    nobs <- 10000
    ndim <- 20
    data <- matrix(runif(nobs*ndim), ncol=ndim)

The `findKNN()` method expects a numeric matrix as input with data points as the rows and variables/dimensions as the columns. We indicate that we want to use the KMKNN algorithm by setting `BNPARAM=KmknnParam()` (which is also the default, so this is not strictly necessary here). We could use a VP tree instead by setting `BNPARAM=VptreeParam()`.

    fout <- findKNN(data, k=10, BNPARAM=KmknnParam())
    head(fout$index)

    ##      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
    ## [1,] 8196 8062 5454 8991 3695 4456 2351 9153 5492  9385
    ## [2,] 6855 9974 5145 4374 8669 3509 4197  202 6575  1654
    ## [3,] 9193 6357 8573  158  492 9272 1625 1463 9650  3545
    ## [4,] 3469 7175 5310 2072 3011 4354  209 9976 7209  7787
    ## [5,] 7848 5991 4298 5257 2899 5531 9457 7889 7311   817
    ## [6,] 3380 1305 2584 7206 2499 4583 8138 4804 4424  8307

    head(fout$distance)

    ##           [,1]      [,2]      [,3]      [,4]      [,5]      [,6]      [,7]
    ## [1,] 1.0830825 1.0840079 1.0925842 1.0987089 1.1154806 1.1241577 1.1262541
    ## [2,] 0.9137818 0.9213725 0.9620821 0.9645489 0.9741699 0.9805689 1.0019530
    ## [3,] 0.9392383 1.0427644 1.0489440 1.0529705 1.0552776 1.0620763 1.0695114
    ## [4,] 0.8683043 0.9229621 0.9329104 0.9740085 0.9743233 0.9752475 0.9981356
    ## [5,] 0.9067922 0.9277674 0.9633644 0.9788265 0.9911254 1.0010642 1.0015802
    ## [6,] 0.9334378 0.9856910 1.0331202 1.0651609 1.0849952 1.0851405 1.0859730
    ##           [,8]     [,9]    [,10]
    ## [1,] 1.1301843 1.136466 1.148723
    ## [2,] 1.0048953 1.015604 1.018154
    ## [3,] 1.0813986 1.083556 1.083570
    ## [4,] 0.9993105 1.005160 1.032564
    ## [5,] 1.0300116 1.034624 1.036723
    ## [6,] 1.0905224 1.105057 1.114984

Each row of the `index` matrix corresponds to a point in `data` and contains the row indices in `data` that are its nearest neighbors. For example, the 3rd point in `data` has the following nearest neighbors:

    fout$index[3,]

    ##  [1] 9193 6357 8573  158  492 9272 1625 1463 9650 3545

… with the following distances to those neighbors:

    fout$distance[3,]

    ##  [1] 0.9392383 1.0427644 1.0489440 1.0529705 1.0552776 1.0620763 1.0695114
    ##  [8] 1.0813986 1.0835555 1.0835697

Note that the reported neighbors are sorted by distance.

# 3 Querying k-nearest neighbors

Another application is to identify the k-nearest neighbors in one dataset based on query points in another dataset. Again, we mock up a small data set:

    nquery <- 1000
    ndim <- 20
    query <- matrix(runif(nquery*ndim), ncol=ndim)

We then use the `queryKNN()` function to identify the 5 nearest neighbors in `data` for each point in `query`.

    qout <- queryKNN(data, query, k=5, BNPARAM=KmknnParam())
    head(qout$index)

    ##      [,1] [,2] [,3] [,4] [,5]
    ## [1,] 2827 6806 4510 9524 7143
    ## [2,] 6475 9164 9218 5324 7940
    ## [3,] 2358 7492 6582 4371 3681
    ## [4,] 6770 1509 1962 8259 7997
    ## [5,] 1328  110 1088 9042 7418
    ## [6,] 1630 4159  500 7568 5137

    head(qout$distance)

    ##           [,1]      [,2]      [,3]      [,4]      [,5]
    ## [1,] 1.0060549 1.0099957 1.0240274 1.0491598 1.0495019
    ## [2,] 0.7291079 0.9566622 0.9714249 0.9815270 0.9829133
    ## [3,] 0.9315287 0.9371423 0.9820317 1.0882948 1.0984504
    ## [4,] 0.9080521 0.9415054 0.9447102 0.9626292 0.9783061
    ## [5,] 0.8181125 0.8218580 0.8521564 0.9436925 1.0071166
    ## [6,] 0.9300248 0.9488922 0.9656993 0.9785690 0.9957626

Each row of the `index` matrix contains the row indices in `data` that are the nearest neighbors of a point in `query`. For example, the 3rd point in `query` has the following nearest neighbors in `data`:

    qout$index[3,]

    ## [1] 2358 7492 6582 4371 3681

… with the following distances to those neighbors:

    qout$distance[3,]

    ## [1] 0.9315287 0.9371423 0.9820317 1.0882948 1.0984504

Again, the reported neighbors are sorted by distance.

# 4 Further options

Users can perform the search for a subset of query points using the `subset=` argument. This yields the same result as but is more efficient than performing the search for all points and subsetting the output.

    findKNN(data, k=5, subset=3:5)

    ## $index
    ##      [,1] [,2] [,3] [,4] [,5]
    ## [1,] 9193 6357 8573  158  492
    ## [2,] 3469 7175 5310 2072 3011
    ## [3,] 7848 5991 4298 5257 2899
    ##
    ## $distance
    ##           [,1]      [,2]      [,3]      [,4]      [,5]
    ## [1,] 0.9392383 1.0427644 1.0489440 1.0529705 1.0552776
    ## [2,] 0.8683043 0.9229621 0.9329104 0.9740085 0.9743233
    ## [3,] 0.9067922 0.9277674 0.9633644 0.9788265 0.9911254

If only the indices are of interest, users can set `get.distance=FALSE` to avoid returning the matrix of distances. This will save some time and memory.

    names(findKNN(data, k=2, get.distance=FALSE))

    ## [1] "index"

It is also simple to speed up functions by parallelizing the calculations with the BiocParallel framework.

    library(BiocParallel)
    out <- findKNN(data, k=10, BPPARAM=MulticoreParam(3))

For multiple queries to a constant `data`, the pre-clustering can be performed in a separate step with `buildIndex()`. The result can then be passed to multiple calls, avoiding the overhead of repeated clustering22 The algorithm type is automatically determined when `BNINDEX` is specified, so there is no need to also specify `BNPARAM` in the later functions..

    pre <- buildIndex(data, BNPARAM=KmknnParam())
    out1 <- findKNN(BNINDEX=pre, k=5)
    out2 <- queryKNN(BNINDEX=pre, query=query, k=2)

Advanced users may also be interested in the `raw.index=` argument, which returns indices directly to the precomputed object rather than to `data`. This may be useful inside package functions where it may be more convenient to work on a common precomputed object.

# 5 Session information

    sessionInfo()

    ## R version 3.6.0 (2019-04-26)
    ## Platform: x86_64-w64-mingw32/x64 (64-bit)
    ## Running under: Windows Server 2012 R2 x64 (build 9600)
    ##
    ## Matrix products: default
    ##
    ## locale:
    ## [1] LC_COLLATE=C
    ## [2] LC_CTYPE=English_United States.1252
    ## [3] LC_MONETARY=English_United States.1252
    ## [4] LC_NUMERIC=C
    ## [5] LC_TIME=English_United States.1252
    ##
    ## attached base packages:
    ## [1] stats     graphics  grDevices utils     datasets  methods   base
    ##
    ## other attached packages:
    ## [1] BiocParallel_1.18.0 BiocNeighbors_1.2.0 knitr_1.22
    ## [4] BiocStyle_2.12.0
    ##
    ## loaded via a namespace (and not attached):
    ##  [1] Rcpp_1.0.1          bookdown_0.9        digest_0.6.18
    ##  [4] stats4_3.6.0        magrittr_1.5        evaluate_0.13
    ##  [7] stringi_1.4.3       S4Vectors_0.22.0    rmarkdown_1.12
    ## [10] tools_3.6.0         stringr_1.4.0       parallel_3.6.0
    ## [13] xfun_0.6            yaml_2.2.0          compiler_3.6.0
    ## [16] BiocGenerics_0.30.0 BiocManager_1.30.4  htmltools_0.3.6

# References

Wang, X. 2012. “A Fast Exact k-Nearest Neighbors Algorithm for High Dimensional Search Using k-Means Clustering and Triangle Inequality.” Proc Int Jt Conf Neural Netw 43 (6):2351–8.

Yianilos, P. N. 1993. “Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces.” In SODA, 93:311–21. 194.