Author name cluster

William B. March

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

JMLR Journal 2015 Journal Article

Plug-and-Play Dual-Tree Algorithm Runtime Analysis

Ryan R. Curtin
Dongryeol Lee
William B. March
Parikshit Ram

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 )

PDF Details

JMLR Journal 2013 Journal Article

MLPACK: A Scalable C++ Machine Learning Library

Ryan R. Curtin
James R. Cline
N. P. Slagle
William B. March
Parikshit Ram
Nishant A. Mehta
Alexander G. Gray

MLPACK is a state-of-the-art, scalable, multi-platform C++ machine learning library released in late 2011 offering both a simple, consistent API accessible to novice users and high performance and flexibility to expert users by leveraging modern features of C++. MLPACK provides cutting-edge algorithms whose benchmarks exhibit far better performance than other leading machine learning libraries. MLPACK version 1.0.3, licensed under the LGPL, is available at www.mlpack.org. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2013. ( edit, beta )

PDF Details

ICML Conference 2013 Conference Paper

Tree-Independent Dual-Tree Algorithms

Ryan R. Curtin
William B. March
Parikshit Ram
David V. Anderson
Alexander G. Gray
Charles Isbell

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.

Details