Plug-and-play dual-tree algorithm runtime analysis
  Numerous machine learning algorithms contain pairwise statistical problems at
their core---that is, tasks that require computations over all pairs of input
points if implemented naively. Often, tree structures are used to solve these
problems efficiently. Dual-tree algorithms can efficiently solve or approximate
many of these problems. Using cover trees, rigorous worst-case runtime
guarantees have been proven for some of these algorithms. In this paper, we
present a problem-independent runtime guarantee for any dual-tree algorithm
using the cover tree, separating out the problem-dependent and the
problem-independent elements. This allows us to just plug in bounds for the
problem-dependent elements to get runtime guarantees for dual-tree algorithms
for any pairwise statistical problem without re-deriving the entire proof. We
demonstrate this plug-and-play procedure for nearest-neighbor search and
approximate kernel density estimation to get improved runtime guarantees. Under
mild assumptions, we also present the first linear runtime guarantee for
dual-tree based range search.
