HackerPapers

arXiv:1304.4327cs.DS

Tree-Independent Dual-Tree Algorithms

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

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

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.

arXiv comments
accepted in ICML 2013
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Nov 2022 to Nov 2022.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Show HN: Explainpaper – Explain jargon in academic papers with GPT-3 1 comment

    • As mentioned in the comments in this thread, it certainly seems useful for non-math-heavy papers. I tried it on a data-structures paper I've been reading: Tree-Independent Dual-Tree Algorithms (https://arxiv.org/pdf/1304.4327.pdf), and I noticed that it had difficulty…

      pncnmnpView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.