# Tree-Independent Dual-Tree Algorithms

arXiv: https://arxiv.org/abs/1304.4327 · HTML: https://mlsanity.com/paper/1304.4327/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2013.

## Built on by (most cited first, 5 of 5)

- [End-to-end Differentiable Clustering with Associative Memories](https://mlsanity.com/paper/2306.03209/) (2023)
- [Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining](https://mlsanity.com/paper/2303.15311/) (2023)
- [Exact Acceleration of K-Means++ and K-Means|](https://mlsanity.com/paper/2105.02936/) (2021)
- [ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain](https://mlsanity.com/paper/2106.04727/) (2021)
- [KNN Implementation Details Can Dramatically Change Performance: An Example from Cover Trees](https://mlsanity.com/paper/2610.16940/) (2026)

## Abstract (arXiv)

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.