Class BKTree

source code

object --+    
         |    
MetricTree --+
             |
            BKTree

"Burkhard-Keller Trees" are unbalanced multiway trees and may grow over time. They belong to the first general solutions to index arbitrary metric spaces.

Every node in a BKTree stores a list of objects which all have a distance of zero to each other, i.e. all objects are considered to be equal by the distance function in use. Additionally, every node keeps a dictionary. In this dictionary, every child is stored, referenceable by its distance to its parent.

Essentially, every node in a BKTree divides its data set S into subsets S^i so that every element in S^i has the distance i to one object arbitrarily picked from S (and stored in this node). For each S^i, a new child node is created and its parent keeps a reference to this child together with its distance.

Insertion of a single object o in a node n is quite easy:

1. If n is empty, store o in n. That's it.
2. Otherwise, calculate its distance to o.
3. If the distance is zero, append this object to the list of objects in this node and return.
4. Otherwise, look for a child of n with the calculated distance to n. If there is such a child, go back to 1. with this child being the new n.
5. Otherwise, create a new node containing o and store it as a child of n with it's calculated distance.

Searching is done recursively by first calculating the distance of the query object to the current node and then using the triangle inequality to determine which children may contain other search results.

Runtime complexity for the construction phase is O(n log(n)), searching is O(n^a) where 0 <= a <= 1. Space requirement is O(n).

This implementation is close to the original description of the algorithm and can only handle discrete distances. If your distance function returns floating point values, it will appear to work at indexing time but will most probably be horribly slow when searching.