The bktrees package

[Tags: bsd3, library]

Burkhard-Keller trees provide an implementation of sets which apart from the ordinary operations also has an approximate member search, allowing you to search for elements that are of a certain distance from the element you are searching for.

[Skip to ReadMe]


Versions0.1, 0.1.1, 0.1.2, 0.1.3, 0.2, 0.2.1, 0.2.2, 0.3, 0.3.1
Change logNone available
Dependenciesarray, base (<4), containers [details]
AuthorJosef Svenningsson
CategoryData Structures
UploadedTue Jun 29 12:07:14 UTC 2010 by JosefSvenningsson
Downloads10346 total (112 in last 30 days)
0 []
StatusDocs uploaded by user
Build status unknown [no reports yet]




splitbaseChoose the new smaller, split-up base package.EnabledAutomatic

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info


Maintainers' corner

For package maintainers and hackage trustees

Readme for bktrees-0.3

This is a module I hacked together quickly after having read the following
blog post:,-Part-1-BK-Trees.html

I thought the data structure sounded cool so I thought it would be an 
interesting excerise to implement it. 

BK-trees can apparently perform very good in some circumstances. The 
paper "Fast Approximate String Matching in a Dictionary" (Baeza-Yates, 
Navarro 1998) recommends them over other structures for doing 
approximate search.

The original paper can be found here:

Henning Günter <> generously supplied two algorithms for
computing the levenshtein edit distance. The better one of the two is used in
the list instance for the Metric class.