The features of Nigh include:


High performance

Nigh uses a variant of a kd-tree which scale logarithmically with the number of elements to search, so it is fast. The data structure batches up values before making space-partitioning decisions that allows for better-balanced trees than without that information. Nigh is a C++ 17 template-based library. The template-based approach means that the compiler builds, and thus optimizes, the resulting data structures specific to its intended usage (i.e., metric space and data type).


Composable metric spaces for robotics problems

Nigh supports real-vector spaces, 2D and 3D rotational spaces, and weighted combinations thereof. For real-vector spaces, Nigh uses Lp metrics with arbitrary integral p > 0, the most common being L1 (Manhattan), L2 (Euclidean), and L (Maximum). For 2D and 3D rotations, Nigh uses the metric of the shortest rotational angle required to transform between the two.


Support for custom data types

Nigh searches based upon a key type returned by a functor that operates on the stored value type. Out of the box, the key types supported by Nigh include Eigen 3's Matrix, Arrays, Quaternions, and Rotation2D; floating point scalars; and STL vectors, arrays, tuples, and pairs. In addition, with the definition of a small traits class Nigh will support arbitrary key types.


Concurrent wait-free inserts and searches

Nigh supports provably concurrent inserts and searches. This means that multiple threads can simultaneously insert into and query the data structure without requiring a lock. Queries are always wait-free. Inserts only wait on concurrent inserts in the same portion of the tree; with random inserts, the probability of waiting diminishes asymptotically to zero. This property makes it ideal for creating multi-core sampling-based motion planners such as those in MPT.


Fallback for unsupported and non-metric spaces

Nigh supports non-metric spaces and provides fallback behavior for unsupported metric spaces under a single reusable and automated API. When using an unsupported metric space with low or no concurrency requirements, Nigh provides a locked version of GNAT. When using any unsupported space with high concurrency requirements, Nigh provides a lock-free linked list implementation.


C++ 17 header-only library

The latest C++ standard provides a wealth of capabilities that ease development of template-based programs while remaining compatible with existing C and C++ software libraries. A header-only library means that code is only compiled if your application needs it, which can ease deployment.


Usage

Nigh data structures are similar in nature to STL maps and unordered_map: they store values and support fast key-based lookup. The difference is that instead of performing lookups based upon a monotonic order or hash as in STL, Nigh's key-based lookup is based upon proximity in a metric space. A metric space is a mathematical set (e.g., real vectors, rotations, etc.), combined with a metric. In Nigh, the set is defined by a data type (e.g., Eigen 3 vector, quaternion, etc.), and the metric is defined by a function that takes two values returns a non-negative scalar representing the distance between the two arguments.

Creating a Nigh data structure requires providing template arguments for (1) the stored data type, (2) the metric space, (3) a functor to access the key from the stored data type, (4) a concurrency level, and (5) the nearest neighbor algorithm.

The stored data type (1) can be any copyable C++ type. Values will be copied into the data structure on insert, and copies will be returned on queries. Some underlying data structures also support inserts with move semantics for additional efficiency.

The metric space (2) is a class that provides a definition of the key type (the mathematical set) and metric (a function). The functor that accesses the key returns a const reference to the key, given the data type. The concurrency level determines what level of concurrent operations to support. The nearest neighbor algorithm determines how the structure organizes the data to support lookup. Nigh provides efficient searching on Lp, SO(2), SO(3), and weighted combinations thereof using its built-in types. Other metric and non-metric spaces are supported as well, though without the same efficiency.

The functor (3) takes the stored data type as an argument and returns a constant reference to its key.

The concurrency level (4) is a tag that specifies the type of concurrent operations to support, and can be one of three levels: (a) fully concurrent queries and inserts, (b) concurrent read-only, or (c) no thread safety.

The nearest neighbor algorithm (5) is a tag class that specifies what nearest neighbor searching algorithm to use. It can be one of: (a) kd-tree with fixed-capacity leaves, (b) static-to-dynamic median balanced kd-trees, (c) GNAT, or (d) linear. Each algorithm has its benefits and pitfalls.

using Key = Eigen::Vector3f;

struct Node { // (1)
    Key key_;
    std::string data_;
};

struct KeyFn { // (3)
    const Key& operator() (const Node& n) const {
        return n.key_;
    }
};

int main() {
  namespace nigh = unc::robotics::nigh;

  using Space = nigh::L2Space<float, 3>; // (2)
  using Con = nigh::Concurrent; // (4)
  using Alg = nigh::KDTreeBatch<>; // (5)

  // create the data structure
  nigh::Nigh<Node, Space, KeyFn, Con, Alg> nn;
    
  // insert a value
  nn.insert(Node{Key{1.2f, 3.4f, 5.6f}, "data"});
  // ...
    
  // here's our query point
  Key query(2.3f, 4.1f, 5.0f);

  // find the nearest neighbor
  std::optional<std::pair<Node, float>> pt =
      nn.nearest(query);

  // find the k-nearest neighbors
  std::size_t k = 10;
  std::vector<std::pair<Node, float>> nbh;
  nn.nearest(nbh, query, k);
}
              

Releases

Nigh is available on GitHub.


Requirements

Nigh requires a C++ 17 capable compiler, and has been tested on clang 5+ and GCC 7+.

Nigh optionally uses the Eigen 3 linear algebra library.


Citing Nigh

If you use Nigh in your research, please cite the following paper(s) as appropriate:

  • Jeffrey Ichnowski and Ron Alterovitz, “Concurrent Nearest-Neighbor Searching for Parallel Sampling-based Motion Planning in SO(3), SE(3), and Euclidean Topologies,“ in Algorithmic Foundations of Robotics (WAFR 2018), Dec. 2018, pp. 1-16. (PDF)
  • Jeffrey Ichnowski and Ron Alterovitz, “Fast Nearest Neighbor Search in SE(3) for Sampling-Based Motion Planning,” in Algorithmic Foundations of Robotics XI (WAFR 2014), H. L. Akin et al. (Eds.), STAR vol. 107, Springer, Aug. 2014, pp. 197-214. (PDF)