Search Nearest Neighbors

Description

Fast k-nearest neighbor searching algorithms including a kd-tree, cover-tree and the algorithm implemented in class package.

Usage

  knn.index(data, k=10, algorithm=c("kd_tree", "cover_tree", "CR", "brute"))
  knnx.index(data, query, k=10, algorithm=c("kd_tree", "cover_tree", "CR", "brute"))

Arguments

Value

return the indice of k nearest neighbors.

Author(s)

Shengqiao Li. To report any bugs or suggestions please email: shli@stat.wvu.edu.

References

Bentley J.L. (1975), “Multidimensional binary search trees used for associative search,” Communication ACM, 18, 309-517.

Arya S. and Mount D.M. (1993), “Approximate nearest neighbor searching,” Proc. 4th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA'93), 271-280.

Arya S., Mount D.M., Netanyahu N.S., Silverman R. and Wu A.Y. (1998), “An optimal algorithm for approximate nearest neighbor searching,” Journal of the ACM, 45, 891-923.

Beygelzimer A., Kakade S. and Langford J. (2006), “Cover trees for nearest neighbor,” ACM Proc. 23rd international conference on Machine learning, 148, 97-104.

See Also

knn.dist and get.knn.

Examples

  data<- query<- cbind(1:10, 1:10)

  knn.index(data, k=5)
  knnx.index(data, query, k=5)
  knnx.index(data, query, k=5, algo="kd_tree")

Results

R version 3.3.1 (2016-06-21) -- "Bug in Your Hair"
Copyright (C) 2016 The R Foundation for Statistical Computing
Platform: x86_64-pc-linux-gnu (64-bit)

R is free software and comes with ABSOLUTELY NO WARRANTY.
You are welcome to redistribute it under certain conditions.
Type 'license()' or 'licence()' for distribution details.

R is a collaborative project with many contributors.
Type 'contributors()' for more information and
'citation()' on how to cite R or R packages in publications.

Type 'demo()' for some demos, 'help()' for on-line help, or
'help.start()' for an HTML browser interface to help.
Type 'q()' to quit R.

> library(FNN)
> png(filename="/home/ddbj/snapshot/RGM3/R_CC/result/FNN/knn.index.Rd_%03d_medium.png", width=480, height=480)
> ### Name: knn.index
> ### Title: Search Nearest Neighbors
> ### Aliases: knn.index knnx.index
> ### Keywords: manip
> 
> ### ** Examples
> 
>   data<- query<- cbind(1:10, 1:10)
> 
>   knn.index(data, k=5)
      [,1] [,2] [,3] [,4] [,5]
 [1,]    2    3    4    5    6
 [2,]    1    3    4    5    6
 [3,]    2    4    1    5    6
 [4,]    3    5    2    6    1
 [5,]    4    6    3    7    2
 [6,]    7    5    8    4    9
 [7,]    8    6    9    5   10
 [8,]    9    7   10    6    5
 [9,]   10    8    7    6    5
[10,]    9    8    7    6    5
>   knnx.index(data, query, k=5)
      [,1] [,2] [,3] [,4] [,5]
 [1,]    1    2    3    4    5
 [2,]    2    1    3    4    5
 [3,]    3    2    4    1    5
 [4,]    4    3    5    2    6
 [5,]    5    4    6    3    7
 [6,]    6    7    5    8    4
 [7,]    7    8    6    9    5
 [8,]    8    9    7   10    6
 [9,]    9   10    8    7    6
[10,]   10    9    8    7    6
>   knnx.index(data, query, k=5, algo="kd_tree")
      [,1] [,2] [,3] [,4] [,5]
 [1,]    1    2    3    4    5
 [2,]    2    1    3    4    5
 [3,]    3    2    4    1    5
 [4,]    4    3    5    2    6
 [5,]    5    4    6    3    7
 [6,]    6    7    5    8    4
 [7,]    7    8    6    9    5
 [8,]    8    9    7   10    6
 [9,]    9   10    8    7    6
[10,]   10    9    8    7    6
> 
> 
> 
> 
> 
> 
> dev.off()
null device 
          1 
>