BK-tree

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]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Tree — /tree/, n. Sir Herbert Beerbohm /bear bohm/, (Herbert Beerbohm), 1853 1917, English actor and theater manager; brother of Max Beerbohm. * * * I Woody perennial plant. Most trees have a single self supporting trunk containing woody tissues, and in …   Universalium

  • Tree — (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree, oak, do ry… …   The Collaborative International Dictionary of English

  • Tree bear — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree beetle — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree bug — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree cat — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree clover — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree crab — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree creeper — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree cricket — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree crow — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”