BK-tree Java library
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.



A Java BK-tree library.

BK-trees offer a simple index of elements in a metric space that allows for searching the tree for elements within a certain distance of the search query with sub-linear efficiency.

For example, a BK-tree with string elements and a metric like the Damerau–Levenshtein distance can serve as a fuzzy search index.

Example usage

import edu.gatech.gtri.bktree.*;
import edu.gatech.gtri.bktree.BkTreeSearcher.Match;
import java.util.Set;
// The Hamming distance is a simple metric that counts the number
// of positions on which the strings (of equal length) differ.
Metric<String> hammingDistance = new Metric<String>() {
    public int distance(String x, String y) {

        if (x.length() != y.length())
            throw new IllegalArgumentException();

        int distance = 0;

        for (int i = 0; i < x.length(); i++)
            if (x.charAt(i) != y.charAt(i))

        return distance;

MutableBkTree<String> bkTree = new MutableBkTree<>(hammingDistance);
bkTree.addAll("berets", "carrot", "egrets", "marmot", "packet", "pilots", "purist");

BkTreeSearcher<String> searcher = new BkTreeSearcher<>(bkTree);

Set<Match<? extends String>> matches = searcher.search("parrot", 2);

for (Match<? extends String> match : matches)
        "%s (distance %d)",

// Output:
//   marmot (distance 2)
//   carrot (distance 1)

Release artifacts

This project's release artifacts are available in the Maven Central Repository.