Mnemonist - KD Tree

A KDTree, or k-dimensional tree, is a data structure used to index points in a multidimensional euclidean space so that it becomes efficient to make proximity queries, such as finding the nearest neighbor of a given point.

For more information about the KDTree, you can head here.

const KDTree = require('mnemonist/kd-tree');

Constructor

Since you need to know the whole list of items to be indexed beforehand, you cannot construct the KDTree. Instead, you can only build one from an iterable or axes using the static #.from or #.fromAxes methods.

Note that the tree is always built in O(n log n) time.

Static #.from

A KDTree can be built from an iterable yielding items looking like this:

[label, [x, y, z...]]

const data = [
  ['zero', [2, 3]],
  ['one', [5, 4]],
  ['two', [9, 6]],
  ['three', [4, 7]],
  ['four', [8, 1]],
  ['five', [7, 2]]
];

const tree = KDTree.from(data, 2);

Static #.fromAxes

For better memory efficiency, or just because you organized your data thusly, you can also build a KDTree from axes with optional labels. If you don’t provide labels, the tree will simply return indices to you when querying.

const axes = [
  [2, 5, 9, 4, 8, 7],
  [3, 4, 6, 7, 1, 2]
];

const labels = ['zero', 'one', 'two', 'three', 'four', 'five'];

const tree = KDTree.fromAxes(axes, labels);
// Or, without labels:
const tree = KDTree.fromAxes(axes);

Methods

Read

#.size

Total number of items stored in the tree.

const data = [
  ['zero', [2, 3]],
  ['one', [5, 4]],
  ['two', [9, 6]],
  ['three', [4, 7]],
  ['four', [8, 1]],
  ['five', [7, 2]]
];

const tree = KDTree.from(data, 2);

tree.size
>>> 6

#.dimensions

Number of dimensions of the space indexed by the tree.

const data = [
  ['zero', [2, 3]],
  ['one', [5, 4]],
  ['two', [9, 6]],
  ['three', [4, 7]],
  ['four', [8, 1]],
  ['five', [7, 2]]
];

const tree = KDTree.from(data, 2);

tree.dimensions
>>> 2

#.nearestNeighbor

Returns query point’s nearest neighbor in the tree.

const data = [
  ['zero', [2, 3]],
  ['one', [5, 4]],
  ['two', [9, 6]],
  ['three', [4, 7]],
  ['four', [8, 1]],
  ['five', [7, 2]]
];

const tree = KDTree.from(data, 2);

tree.nearestNeighbor([2, 4]);
>>> 'zero'

#.kNearestNeighbors

Returns query point’s k nearest neighbors in the tree, sorted from closest to farthest.

const data = [
  ['zero', [2, 3]],
  ['one', [5, 4]],
  ['two', [9, 6]],
  ['three', [4, 7]],
  ['four', [8, 1]],
  ['five', [7, 2]]
];

const tree = KDTree.from(data, 2);

tree.kNearestNeighbors(2, [2, 4]);
>>> ['zero', 'one']