Tree-Independent Dual-Tree Algorithms


Ryan Curtin, William March, Parikshit Ram, David Anderson, Alexander Gray, Charles Isbell ;
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):1435-1443, 2013.


Dual-tree algorithms are a widely used class of branch-and-bound algorithms. Unfortunately, developing dual-tree algorithms for use with different trees and problems is often complex and burdensome. We introduce a four-part logical split: the tree, the traversal, the point-to-point base case, and the pruning rule. We provide a meta-algorithm which allows development of dual-tree algorithms in a tree-independent manner and easy extension to entirely new types of trees. Representations are provided for five common algorithms; for k-nearest neighbor search, this leads to a novel, tighter pruning bound. The meta-algorithm also allows straightforward extensions to massively parallel settings.

Related Material