bktrees: A set data structure with approximate searching

[ bsd3, data-structures, library ] [ Propose Tags ] [ Report a vulnerability ]

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]

Modules

[Index]

Data
- Set
  - Data.Set.BKTree
    - Data.Set.BKTree.Internal

Flags

Automatic Flags

Name	Description	Default
splitbase	Choose the new smaller, split-up base package.	Enabled

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

Downloads

bktrees-0.3.1.tar.gz [browse] (Cabal source package)
Package description (as included in the package)

Maintainer's Corner

Package maintainers

JosefSvenningsson

For package maintainers and hackage trustees

edit package information

Candidates

No Candidates

Versions [RSS]	0.1, 0.1.1, 0.1.2, 0.1.3, 0.2, 0.2.1, 0.2.2, 0.3, 0.3.1
Dependencies	array, base (<5), containers [details]
License	BSD-3-Clause
Author	Josef Svenningsson
Maintainer	josef.svenningsson@gmail.com
Category	Data Structures
Source repo	head: darcs get http://patch-tag.com/r/josef/bktrees
Uploaded	by JosefSvenningsson at 2010-11-22T23:23:44Z
Distributions	NixOS:0.3.1
Reverse Dependencies	2 direct, 3 indirect [details]
Downloads	16869 total (31 in the last 30 days)
Rating	(no votes yet) [estimated by Bayesian average]
Your Rating	λ λ λ
Status	Docs uploaded by user Build status unknown [no reports yet]

Readme for bktrees-0.3.1

[back to package description]

This is a module I hacked together quickly after having read the following
blog post:
http://blog.notdot.net/archives/30-Damn-Cool-Algorithms,-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.
http://citeseer.ist.psu.edu/1593.html

The original paper can be found here:
http://portal.acm.org/citation.cfm?id=362003.362025

Henning Günter <h.guenther@tu-bs.de> 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.