BiocNeighbors 1.2.0
The BiocNeighbors package provides several algorithms for approximate neighbor searches:
These methods complement the exact algorithms described previously.
Again, it is straightforward to switch from one algorithm to another by simply changing the BNPARAM
argument in findKNN
and queryKNN
.
We perform the k-nearest neighbors search with the Annoy algorithm by specifying BNPARAM=AnnoyParam()
.
nobs <- 10000
ndim <- 20
data <- matrix(runif(nobs*ndim), ncol=ndim)
fout <- findKNN(data, k=10, BNPARAM=AnnoyParam())
head(fout$index)
## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
## [1,] 2518 960 4651 3041 4593 9968 8204 148 9109 5322
## [2,] 7182 7627 480 167 2686 9737 7865 8253 4963 6519
## [3,] 96 8041 737 3280 6599 9222 2716 6781 2631 5531
## [4,] 1110 3395 6911 4060 6786 9344 5618 6930 6946 8445
## [5,] 6667 6231 5911 5863 333 9098 97 6999 7902 108
## [6,] 8000 3855 7572 1638 3080 9730 4500 9249 1871 7343
head(fout$distance)
## [,1] [,2] [,3] [,4] [,5] [,6] [,7]
## [1,] 0.9886118 1.0789745 1.1011719 1.1072190 1.1282983 1.1313829 1.1483887
## [2,] 0.9678174 0.9989009 1.0001528 1.0149844 1.0430777 1.0773309 1.0787989
## [3,] 0.8530040 0.8537472 0.8600176 0.9204907 0.9455487 0.9627153 0.9936166
## [4,] 0.9085732 0.9782447 1.0332650 1.0345398 1.0529071 1.0630660 1.1026986
## [5,] 0.8995217 0.9690334 1.0282756 1.0286645 1.0287858 1.0454463 1.0488964
## [6,] 0.9976661 1.0789716 1.0794306 1.1559469 1.1651425 1.1816528 1.1842009
## [,8] [,9] [,10]
## [1,] 1.153453 1.160346 1.161580
## [2,] 1.093732 1.102553 1.103060
## [3,] 1.010614 1.025963 1.028584
## [4,] 1.135454 1.137568 1.138443
## [5,] 1.053010 1.055878 1.069182
## [6,] 1.184640 1.189335 1.194872
We can also identify the k-nearest neighbors in one dataset based on query points in another dataset.
nquery <- 1000
ndim <- 20
query <- matrix(runif(nquery*ndim), ncol=ndim)
qout <- queryKNN(data, query, k=5, BNPARAM=AnnoyParam())
head(qout$index)
## [,1] [,2] [,3] [,4] [,5]
## [1,] 6388 1238 8748 4223 7113
## [2,] 3568 713 3653 9873 7198
## [3,] 6606 5190 8826 8325 168
## [4,] 2999 7547 1646 7016 667
## [5,] 3825 6983 7762 6548 8791
## [6,] 76 673 6958 5864 1673
head(qout$distance)
## [,1] [,2] [,3] [,4] [,5]
## [1,] 0.8677352 0.8680670 0.8719941 0.9507282 0.9643818
## [2,] 0.9030752 0.9831578 1.0177069 1.0188230 1.0511543
## [3,] 0.8654836 0.9786622 0.9809887 0.9890227 1.0002736
## [4,] 0.9947681 1.0191822 1.0230621 1.0469787 1.0477513
## [5,] 0.7239743 1.0286745 1.0508665 1.0740196 1.0862203
## [6,] 0.9796220 1.0947175 1.1007018 1.1038973 1.1076198
It is similarly easy to use the HNSW algorithm by setting BNPARAM=HnswParam()
.
Most of the options described for the KMKNN algorithm are also applicable here. For example:
subset
to identify neighbors for a subset of points.get.distance
to avoid retrieving distances when unnecessary.BPPARAM
to parallelize the calculations across multiple workers.BNINDEX
to build the forest once for a given data set and re-use it across calls.The use of a pre-built BNINDEX
is illustrated below:
pre <- buildIndex(data, BNPARAM=AnnoyParam())
out1 <- findKNN(BNINDEX=pre, k=5)
out2 <- queryKNN(BNINDEX=pre, query=query, k=2)
Users are referred to the documentation of each function for specific details on the available arguments.
The forest of trees form an indexing structure that is saved to file.
By default, this file is located in tempdir()
1 On HPC file systems, you can change TEMPDIR
to a location that is more amenable to parallelized access. and will be removed when the session finishes.
AnnoyIndex_path(pre)
## [1] "C:\\Users\\biocbuild\\bbs-3.9-bioc\\tmpdir\\Rtmp2njyY7\\file1d8061e27de7.idx"
If the index is to persist across sessions, the path of the index file can be directly specified in buildIndex
.
However, this means that it becomes the responsibility of the user to clean up any temporary indexing files after calculations are complete.
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] BiocNeighbors_1.2.0 knitr_1.22 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] BiocParallel_1.18.0 tools_3.6.0 stringr_1.4.0
## [13] parallel_3.6.0 xfun_0.6 yaml_2.2.0
## [16] compiler_3.6.0 BiocGenerics_0.30.0 BiocManager_1.30.4
## [19] htmltools_0.3.6