Bk-tree
Jump to navigation
Jump to search
A Bk-tree is a metric tree suggested by Burkhard and Keller 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 .
References and external links
- ^ 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.
- ^ Ricardo Baeza-Yates and Gonzalo Navarro. Fast Approximate String Matching in a Dictionary. Proc. SPIRE'98