BK-tree

A BK-tree is a metric tree suggested by Burkhard and Keller ref|BK73 specifically adapted to discrete metric spaces.For simplicity, let us consider integer discrete metric $varrho(x,y)$. 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 $varrho(a,b)\; =\; k$. BK-trees can be used for approximate string matching in a dictionary ref|BN98.

References

* [http://doi.acm.org/10.1145/362003.362025 W. Burkhard and R. Keller. Some approaches to best-match file searching, CACM, 1973]
* R. Baeza-Yates, W. Cunto, U. Manber, and S. Wu. Proximity matching using fixed queries trees. In M. Crochemore and D. Gusfield, editors, 5th Combinatorial Pattern Matching, LNCS 807, pages 198-212, Asilomar, CA, June 1994.
* [http://www.dcc.uchile.cl/~gnavarro/ps/spire98.2.ps.gz Ricardo Baeza-Yates and Gonzalo Navarro. Fast Approximate String Matching in a Dictionary. Proc. SPIRE'98]

External links

* A BK-tree implementation in [http://cliki.net/bk-tree lisp] with cool test results and performance graphs.
* BK-tree implementation written in [http://hupp.org/adam/weblog/2007/10/28/burkhard-keller-bk-trees-in-python/ Python] and its a port to [http://hupp.org/adam/hg/bktree/file/tip/BKTree.hs Haskell] .
* A good explanation of BK-Trees and their relationship to metric spaces [http://blog.notdot.net/archives/30-Damn-Cool-Algorithms,-Part-1-BK-Trees.html Damn Cool Algorithms, Part 1: BK-Trees]