Wraps 'libnabo', a Fast K Nearest Neighbour Library for Low Dimensions

An R wrapper for 'libnabo', an exact or approximate k nearest neighbour library which is optimised for low dimensional spaces (e.g. 3D). 'libnabo' has speed and space advantages over the 'ANN' library wrapped by package 'RANN'. 'nabor' includes a knn function that is designed as a drop-in replacement for 'RANN' function nn2. In addition, objects which include the k-d tree search structure can be returned to speed up repeated queries of the same set of target points.


DOI Release Version CRAN_Status_Badge Build Status

R package nabor wraps libnabo, a fast K Nearest Neighbour library for low-dimensional spaces implemented in templated C++. In comparison with the widely used ANN library (wrapped by the RANN R package), libnabo is reported to be 5% to 20% faster with more compact data structures.

Quick start

# install (see below for details)
install.packages("nabor")
 
# use
library(nabor)
 
# help
?nabor
?knn
 
# run examples
example(knn)
example(WKNN)
 
# run tests
library(testthat)
test_package("nabor")
 
# cite
citation("nabor")

nabor vs RANN

For R users nabor provides a function, knn, that is a drop in replacement for the nn2 function in the RANN R package. I have seen speedups of 2-3x fold for queries of interest (a few thousand points in 3d, k=1) when comparing nabor::knn and RANN::nn2. See ?knn for details.

Furthermore nabor provides a mechanism for reusing the k-d search tree structure for multiple queries. This is achieved by wrapping a libnabo k-d tree and associated points into a C++ class. This in turn is wrapped as an R reference class (by RcppModules) that can be used in R. See ?WKNN for details. The WKNNF class has the additional feature of using floats (4 bytes per coordinate) for the underlying storage, rather than the doubles used by R; this may be useful for large pointsets.

Installation

Released version from CRAN

The current stable version of the package is available from CRAN. The package requires compilation, but installing from CRAN allows mac and windows users without the full C++ compiler toolchain to install binary packages.

install.packages("nabor")

Development version from github

The nabor package is known to compile from source with the standard C(++) compiler toolchains for R under MacOS X, Windows and Linux. See https://www.rstudio.com/products/rpackages/devtools/ for details of the developer toolchains needed for your platform.

Once you have installed the appropriate developer toolchain mentioned above, you can use the devtools package to install the development version of the package:

if (!require("devtools")) install.packages("devtools")
devtools::install_github("jefferis/nabor")

Dependencies

The nabor package includes libnabo and all of its dependencies (boost, via package BH) and Eigen (via package RcppEigen) and does not depend on any non-standard system libraries. It should therefore run out of the box on any mac/linux/windows system.

Acknowlegements

libnabo and therefore the nabor R package are released under the BSD 3 clause license. If you make use of nabor please cite the original authors:


Elseberg J, Magnenat S, Siegwart R and Nüchter A (2012). “Comparison of nearest-neighbor-search
strategies and implementations for efficient shape registration.” _Journal of Software Engineering for
Robotics (JOSER)_, *3*(1), pp. 2-12. ISSN 2035-3928.

A BibTeX entry for LaTeX users is

  @Article{elsebergcomparison,
    title = {Comparison of nearest-neighbor-search strategies and implementations for efficient shape registration},
    author = {J. Elseberg and S. Magnenat and R. Siegwart and A. N{\"u}chter},
    journal = {Journal of Software Engineering for Robotics (JOSER)},
    pages = {2--12},
    volume = {3},
    number = {1},
    year = {2012},
    issn = {2035-3928},
  }

nabor also makes use of the tremendous Rcpp and RcppEigen packages – kudos to their authors!

News

nabor 0.5.0

  • add radius bounded search (#6, #7)
  • remove register keyword from C++ libnabo (#9)

nabor 0.4.7

  • dev: register native routines as recommended for R 3.4.0
  • dev: update travis

nabor 0.4.6

  • make RANN test conditional
  • Fix description for R 3.2.0
  • roxygen2/Rcpp updates

nabor 0.4.5

nabor 0.4.4

  • fixes warning for non-portable Makefile (thanks to Brian Ripley)

nabor 0.4.3

  • fixes a UBSAN error in libnabo (thanks to Brian Ripley)

nabor 0.4.2

  • license fixes for CRAN (include GJ as copyright holder)

nabor 0.4.1

  • CRAN release
  • insist on RcppEigen >= 0.3.2.2.0 (conservative but should not be restrictive)

nabor 0.4

  • corectly handle non-floating point input to knn (and note that WKNN classes must be initialised with floating point input)
  • standardise method names of WKNN classes so that they are identical for WKNND and WKNNF objects
  • doc: improve main package docs
  • dev: templatise WKNN C++ classes

nabor 0.3

  • preparing for CRAN
  • rename package from nabo to nabor
  • fix handling of non-matrix inputs by knn
  • knn performs self-query when query is missing
  • dev: only link to RcppEigen
  • dev: remove boost/any.hpp header and insist on latest BH package (>= 1.54.0-4) (also bumps R requirement to 3.0.2).

nabor 0.2

  • first public version (github)
  • includes knn function (with different search types, defaulting to auto)
  • ... and WKNNF and WKNND classes that wrap a tree object

Reference manual

It appears you don't have a PDF plugin for this browser. You can click here to download the reference manual.

install.packages("nabor")

0.5.0 by Gregory Jefferis, 6 months ago


https://github.com/jefferis/nabor https://github.com/ethz-asl/libnabo


Report a bug at https://github.com/jefferis/nabor/issues


Browse source code at https://github.com/cran/nabor


Authors: Stephane Mangenat (for 'libnabo') , Gregory Jefferis


Documentation:   PDF Manual  


BSD_3_clause + file LICENSE license


Imports Rcpp, methods

Suggests testthat, RANN

Linking to Rcpp, RcppEigen, BH


Imported by STMedianPolish, angstroms, filling, mgwrsar, nat, nat.nblast, rcss, stplanr.

Suggested by nat.templatebrains.


See at CRAN