smile.neighbor

Class KDTree<E>

java.lang.Object

smile.neighbor.KDTree<E>

Type Parameters:

E - the type of data objects in the tree.

All Implemented Interfaces:

KNNSearch<double[],E>, NearestNeighborSearch<double[],E>, RNNSearch<double[],E>

public class KDTree<E>
extends java.lang.Object
implements NearestNeighborSearch<double[],E>, KNNSearch<double[],E>, RNNSearch<double[],E>

A KD-tree (short for k-dimensional tree) is a space-partitioning dataset structure for organizing points in a k-dimensional space. KD-trees are a useful dataset structure for nearest neighbor searches. The kd-tree is a binary tree in which every node is a k-dimensional point. Every non-leaf node generates a splitting hyperplane that divides the space into two subspaces. Points left to the hyperplane represent the left sub-tree of that node and the points right to the hyperplane by the right sub-tree. The hyperplane direction is chosen in the following way: every node split to sub-trees is associated with one of the k-dimensions, such that the hyperplane is perpendicular to that dimension vector. So, for example, if for a particular split the "x" axis is chosen, all points in the subtree with a smaller "x" value than the node will appear in the left subtree and all points with larger "x" value will be in the right sub tree.

KD-trees are not suitable for efficiently finding the nearest neighbor in high dimensional spaces. As a general rule, if the dimensionality is D, then number of points in the dataset, N, should be N >> 2^D. Otherwise, when kd-trees are used with high-dimensional dataset, most of the points in the tree will be evaluated and the efficiency is no better than exhaustive search, and approximate nearest-neighbor methods should be used instead.

By default, the query object (reference equality) is excluded from the neighborhood. You may change this behavior with setIdenticalExcluded. Note that you may observe weird behavior with String objects. JVM will pool the string literal objects. So the below variables String a = "ABC"; String b = "ABC"; String c = "AB" + "C"; are actually equal in reference test a == b == c. With toy data that you type explicitly in the code, this will cause problems. Fortunately, the data would be read from secondary storage in production.

Constructor Summary

Constructors

Constructor and Description
KDTree(double[][] key, E[] data) Constructor.

Method Summary

Modifier and Type	Method and Description
boolean	isIdenticalExcluded() Get whether if query object self be excluded from the neighborhood.
Neighbor<double[],E>[]	knn(double[] q, int k) Search the k nearest neighbors to the query.
Neighbor<double[],E>	nearest(double[] q) Search the nearest neighbor to the given sample.
void	range(double[] q, double radius, java.util.List<Neighbor<double[],E>> neighbors) Search the neighbors in the given radius of query object, i.e.
KDTree<E>	setIdenticalExcluded(boolean excluded) Set if exclude query object self from the neighborhood.
java.lang.String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

KDTree

public KDTree(double[][] key,
              E[] data)

Constructor.

Parameters:

key - the keys of data objects.

data - the data objects.

Method Detail

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

setIdenticalExcluded

public KDTree<E> setIdenticalExcluded(boolean excluded)

Set if exclude query object self from the neighborhood.

isIdenticalExcluded

public boolean isIdenticalExcluded()

Get whether if query object self be excluded from the neighborhood.

nearest

public Neighbor<double[],E> nearest(double[] q)

Description copied from interface: NearestNeighborSearch

Search the nearest neighbor to the given sample.

Specified by:

nearest in interface NearestNeighborSearch<double[],E>

Parameters:

q - the query key.

Returns:

the nearest neighbor

knn

public Neighbor<double[],E>[] knn(double[] q,
                                  int k)

Description copied from interface: KNNSearch

Search the k nearest neighbors to the query.

Specified by:

knn in interface KNNSearch<double[],E>

Parameters:

q - the query key.

k - the number of nearest neighbors to search for.

range

public void range(double[] q,
                  double radius,
                  java.util.List<Neighbor<double[],E>> neighbors)

Description copied from interface: RNNSearch

Search the neighbors in the given radius of query object, i.e. d(q, v) ≤ radius.

Specified by:

range in interface RNNSearch<double[],E>

Parameters:

q - the query key.

radius - the radius of search range from target.

neighbors - the list to store found neighbors in the given range on output.