Bk-tree

From Cosmopedia
Jump to navigation Jump to search

A Bk-tree is a metric tree suggested by Burkhard and Keller [1] specifically adapted to discrete metric spaces. For simplicity, let us consider integer discrete metric <math>\varrho(x,y)</math>. Then, Bk-tree is defined in the following way. An arbitrary element a is selected as root node. Root node may have zero or more subtrees. The k-th subtree is recursively built of all elements b such that <math>\varrho(a,b) = k</math>. Bk-trees can be used for approximate string matching in a dictionary [2].

References and external links

Template:Compu-sci-stub