Package smile.neighbor
Class BKTree<K,V>
java.lang.Object
smile.neighbor.BKTree<K,V>
 Type Parameters:
K
 the type of keys.V
 the type of associated objects.
 All Implemented Interfaces:
Serializable
,RNNSearch<K,
V>
A BKtree is a metric tree specifically adapted to discrete metric spaces.
For simplicity, let us consider integer discrete metric d(x,y). Then,
BKtree is defined in the following way. An arbitrary element
a
is selected as root. Root may have zero or more subtrees. The kth subtree
is recursively built of all elements a
such that
d(a,b) = k
. BKtrees 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 generally read from secondary storage in production.
References
 W. Burkhard and R. Keller. Some approaches to bestmatch file searching. CACM, 1973.
 See Also:

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionvoid
Adds a dataset into BKtree.void
Adds a datum into the BKtree.static <T> BKTree
<T, T> Return a BKtree of the data.static <T> BKTree
<T, T> Return a BKtree of the data.void
Retrieves the neighbors in a fixed radius of query object, i.e.void
Search the neighbors in the given radius of query object, i.e.toString()

Constructor Details

BKTree
Constructor. Parameters:
distance
 the metric used to build BKtree. Note that the metric must be a discrete distance, e.g. edit distance, Hamming distance, Lee distance, Jaccard distance, and taxonomic distance, etc.


Method Details

of
Return a BKtree of the data. Type Parameters:
T
 the type of keys and values. Parameters:
data
 the data objects, which are also used as key.distance
 the metric used to build BKtree. Note that the metric must be a discrete distance, e.g. edit distance, Hamming distance, Lee distance, Jaccard distance, and taxonomic distance, etc. Returns:
 BKtree.

of
Return a BKtree of the data. Type Parameters:
T
 the type of keys and values. Parameters:
data
 the data objects, which are also used as key.distance
 the metric used to build BKtree. Note that the metric must be a discrete distance, e.g. edit distance, Hamming distance, Lee distance, Jaccard distance, and taxonomic distance, etc. Returns:
 BKtree.

toString

add
Adds a datum into the BKtree. Parameters:
key
 the data key.value
 the data object.

add
Adds a dataset into BKtree. Parameters:
data
 the dataset to insert into the BKtree.

search
Description copied from interface:RNNSearch
Retrieves the neighbors in a fixed radius of query object, i.e.d(q, v) <= radius
. 
search
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.
