org.apache.ignite.ml.knn.utils.indices

Class KDTreeSpatialIndex<L>

java.lang.Object

org.apache.ignite.ml.knn.utils.indices.KDTreeSpatialIndex<L>

Type Parameters:

L - Label type.

All Implemented Interfaces:

AutoCloseable, SpatialIndex<L>

public class KDTreeSpatialIndex<L>
extends Object
implements SpatialIndex<L>

KD tree based implementation of SpatialIndex. Asymptotic runtime complexity of finding k closest elements is O(log(n)*k), but it degrades on high dimensional data.

Constructor Summary

Constructors

Constructor and Description
KDTreeSpatialIndex(List<LabeledVector<L>> data, DistanceMeasure distanceMeasure) Constructs a new instance of KD tree spatial index.

Method Summary

Modifier and Type	Method and Description
List<LabeledVector<L>>	findKClosest(int k, Vector pnt) Finds k closest elements to the specified point.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.apache.ignite.ml.knn.utils.indices.SpatialIndex

close

Constructor Detail

KDTreeSpatialIndex

public KDTreeSpatialIndex(List<LabeledVector<L>> data,
                          DistanceMeasure distanceMeasure)

Constructs a new instance of KD tree spatial index. To construct KD tree a "randomized" approach is uses, all nodes are inserted into the tree sequentially without any additional computations and rebalancing.

Parameters:

data - Data points.

distanceMeasure - Distance measure.

Method Detail

findKClosest

public List<LabeledVector<L>> findKClosest(int k,
                                           Vector pnt)

Finds k closest elements to the specified point.

Specified by:

findKClosest in interface SpatialIndex<L>

Parameters:

k - Number of elements to be returned.

pnt - Point to be used to calculate distance to other points.

Returns:

An array of the k closest elements to the specified point.