Tree-Independent Dual-Tree Algorithms
Abstract
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.
Cite
Text
Curtin et al. "Tree-Independent Dual-Tree Algorithms." International Conference on Machine Learning, 2013.Markdown
[Curtin et al. "Tree-Independent Dual-Tree Algorithms." International Conference on Machine Learning, 2013.](https://mlanthology.org/icml/2013/curtin2013icml-treeindependent/)BibTeX
@inproceedings{curtin2013icml-treeindependent,
title = {{Tree-Independent Dual-Tree Algorithms}},
author = {Curtin, Ryan and March, William and Ram, Parikshit and Anderson, David and Gray, Alexander and Isbell, Charles},
booktitle = {International Conference on Machine Learning},
year = {2013},
pages = {1435-1443},
volume = {28},
url = {https://mlanthology.org/icml/2013/curtin2013icml-treeindependent/}
}