Mnemonist

Burkhard-Keller Tree


A BKTree is a data structure that makes possible to make efficient fuzzy query using arbitrary distance metrics such as the Levenshtein distance.

For more information about the Burkhard-Keller Tree, you can head here.

var BKTree = require('mnemonist/bk-tree');

Use case

Let’s say we want to build an autocomplete system.

When the user inputs a string, we are going to search for every term we know being at most at a Levenshtein distance of 2 of the user’s query.

The naive method would be to “brute-force” the list of terms likewise:

var suggestions = terms.filter(term => {
  return levenshtein(term, query) <= 2;
});

But, even if this works with few terms, it will soon become hard to compute if the list of terms grows too much.

Burkhard-Keller trees solves this problem by indexing the list of terms such as it becomes efficient to query them using a distance metric.

var tree = BKTtree.from(terms, levenshtein);

// We can now query the tree easily:
var suggestions = tree.search(2, query);

N.B. you should probably also check the SymSpell structure, which is able to perform the same kind of job but is even more efficient for this precise use case.

Constructor

The BKTree takes a single argument being the distance metric to use.

var tree = new BKTree(distance);

N.B. the given distance metric must return integers. As such, the Jaccard index, for instance, is not suitable to use with this data strucure.

What’s more, only a true metric can be used.

Static #.from

Alternatively, one can build a BKTree from an arbitrary JavaScript iterable likewise:

var tree = BKTree.from(['hello', 'mello'], distance);

Members

Methods

Mutation

Read

#.size

Total number of items stored in the tree.

var tree = new BKTree(distance);

tree.add('hello');

tree.size
>>> 1

#.add

Adds a single item to the tree.

var tree = new BKTree(distance);

tree.add('hello');

#.clear

Completely clears the tree of its items.

var tree = new BKTree(distance);

tree.add('hello');
tree.clear();

tree.size
>>> 0

Returns every item in the tree within the desired distance.

var tree = new BKTree(distance);

tree.add('hello');
tree.add('mello');
tree.add('roman');

tree.search(1, 'vello');
>>> [
  {item: 'hello', distance: 1}
  {item: 'mello', distance: 1}
]