|
BK-tree
A BK-tree is a metric tree suggested by Walter Austin Burkhard and Robert M. Keller specifically adapted to discrete metric spaces. For simplicity, consider integer discrete metric d(x,y). Then, BK-tree is defined in the following way. An arbitrary element ''a'' is selected as root node. The root node 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. Example This picture depicts the BK-tree for the set W of words obtained by using the Levenshtein distance * each node u is labeled by a string of w_u \in W; * each arc (u,v) is labeled by d_ = d(w_u,w_v) where w_u denotes the word assigned to u. The BK-tree is built so that: * for all node u of the BK-tree, the weight assigned to its egress arcs are distinct; * for all arc e=(u,v) labeled by k, each descendant v' of v satisfies the following equation: d(w_u, w_) = k: ** ''Example 1:'' Cons ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Metric Trees
A metric tree is any tree data structure specialized to index data in metric spaces. Metric trees exploit properties of metric spaces such as the triangle inequality to make accesses to the data more efficient. Examples include the M-tree, vp-trees, cover trees, MVP trees, and BK-trees. Multidimensional search Most algorithms and data structures for searching a dataset are based on the classical binary search algorithm, and generalizations such as the k-d tree or range tree work by interleaving the binary search algorithm over the separate coordinates and treating each spatial coordinate as an independent search constraint. These data structures are well-suited for range query problems asking for every point (x,y) that satisfies \mbox_x \leq x \leq \mbox_x and \mbox_y \leq y \leq \mbox_y. A limitation of these multidimensional search structures is that they are only defined for searching over objects that can be treated as vectors. They are not applicable for the more general ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
