Nigh

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 L^p, 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);
}