BK-tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search

A BK-tree is a metric tree suggested by Walter Austin Burkhard and Robert M. Keller[1] 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 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 [2].

References[edit]

External links[edit]

  • A BK-tree implementation in Common Lisp with test results and performance graphs.
  • An explanation of BK-Trees and their relationship to metric spaces [3]