smile.neighbor

Class BKTree<E>

java.lang.Object

smile.neighbor.BKTree<E>

Type Parameters:

E - the type of data objects in the tree.

All Implemented Interfaces:

RNNSearch<E,E>

public class BKTree<E>
extends java.lang.Object
implements RNNSearch<E,E>

A BK-tree is a metric tree specifically adapted to discrete metric spaces. For simplicity, let us consider integer discrete metric d(x,y). Then, BK-tree is defined in the following way. An arbitrary element a is selected as root root. Root may have zero or more subtrees. The k-th subtree is recursively built of all elements b such that d(a,b) = k. BK-trees can be used for approximate string matching in a dictionary.

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.

References

1. W. Burkhard and R. Keller. Some approaches to best-match file searching. CACM, 1973.

Constructor Summary

Constructors

Constructor and Description
BKTree(Metric<E> distance) Constructor.

Method Summary

Modifier and Type	Method and Description
void	add(java.util.Collection<E> data) Add a dataset into BK-tree.
void	add(E datum) Add a datum into the BK-tree.
void	add(E[] data) Add a dataset into BK-tree.
boolean	isIdenticalExcluded() Get whether if query object self be excluded from the neighborhood.
void	range(E q, double radius, java.util.List<Neighbor<E,E>> neighbors) Search the neighbors in the given radius of query object, i.e.
void	range(E q, int radius, java.util.List<Neighbor<E,E>> neighbors) Search the neighbors in the given radius of query object, i.e.
BKTree<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

BKTree

public BKTree(Metric<E> distance)

Constructor.

Parameters:

distance - the metric used to build BK-tree. Note that the metric must be a discrete distance, e.g. edit distance, Hamming distance, Lee distance, Jaccard distance, and taxonomic distance, etc.

Method Detail

add

public void add(E[] data)

Add a dataset into BK-tree.

Parameters:

data - the dataset to insert into the BK-tree.

add

public void add(java.util.Collection<E> data)

Add a dataset into BK-tree.

Parameters:

data - the dataset to insert into the BK-tree.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

add

public void add(E datum)

Add a datum into the BK-tree.

setIdenticalExcluded

public BKTree<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.

range

public void range(E q,
                  double radius,
                  java.util.List<Neighbor<E,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<E,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.

range

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

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

Parameters:

q - the query object.

radius - the radius of search range from target.

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