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. [abs] [ pdf ][ bib ] &copy JMLR 2015. ( edit, beta )

Authors

• Ryan R. Curtin Booz Allen Hamilton
• Dongryeol Lee
• William B. March
• Parikshit Ram International Business Machines

Keywords

No keywords are indexed for this paper.