# 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.

```
var 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...]]
```

```
var data = [
['zero', [2, 3]],
['one', [5, 4]],
['two', [9, 6]],
['three', [4, 7]],
['four', [8, 1]],
['five', [7, 2]]
];
var 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.

```
var axes = [
[2, 5, 9, 4, 8, 7],
[3, 4, 6, 7, 1, 2]
];
var labels = ['zero', 'one', 'two', 'three', 'four', 'five'];
var tree = KDTree.fromAxes(axes, labels);
// Or, without labels:
var tree = KDTree.fromAxes(axes);
```

## Members

## Methods

*Read*

### #.size

Total number of items stored in the tree.

```
var data = [
['zero', [2, 3]],
['one', [5, 4]],
['two', [9, 6]],
['three', [4, 7]],
['four', [8, 1]],
['five', [7, 2]]
];
var tree = new KDTree(data, 2);
tree.size
>>> 6
```

### #.dimensions

Number of dimensions of the space indexed by the tree.

```
var data = [
['zero', [2, 3]],
['one', [5, 4]],
['two', [9, 6]],
['three', [4, 7]],
['four', [8, 1]],
['five', [7, 2]]
];
var tree = new KDTree(data, 2);
tree.dimensions
>>> 2
```

### #.nearestNeighbor

Returns query point’s nearest neighbor in the tree.

```
var data = [
['zero', [2, 3]],
['one', [5, 4]],
['two', [9, 6]],
['three', [4, 7]],
['four', [8, 1]],
['five', [7, 2]]
];
var tree = new KDTree(data, 2);
tree.nearestNeighbor([2, 4]);
>>> 'zero'
```

### #.kNearestNeighbors

Returns query point’s `k`

nearest neighbors in the tree, sorted from closest to farthest.

```
var data = [
['zero', [2, 3]],
['one', [5, 4]],
['two', [9, 6]],
['three', [4, 7]],
['four', [8, 1]],
['five', [7, 2]]
];
var tree = new KDTree(data, 2);
tree.kNearestNeighbors(2, [2, 4]);
>>> ['zero', 'one']
```