BKT

Overview

BKT is a tree structure designed for discrete distance functions. It chooses a pivot as the root, and maintains the objects having the distance i to the pivot in its i^th sub-tree. If a sub-tree contains more than one objects, it selects a pivot at random and partitions the sub-tree recursively. Fig. 1 gives an example BKT. The leaf nodes store the actual objects, while the non-leaf nodes store the corresponding pivots used to partition the sub-trees. Although BKT is designed for discrete distance function, the continuous distance range can be partitioned into discrete ranges used for indexing. For example, if the continuous distance function range is [0, 30], we can divide it into three disjoint ranges [0, 10), [10, 20), [20, 30] in order to simulate the discrete distance function. Hence, BKT can be adapted to support both discrete and continuous distance functions.

Code Usage

The code can be download from SISAP Metric Space Library.