The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

In this paper we consider the problem of finding sets of points that conform to a given underlying model from within a dense, noisy set of observations. This problem is motivated by the task of efficiently linking faint asteroid detections, but is applicable to a range of spatial queries. We survey current tree-based approaches, showing a trade-off exists between single tree and multiple tree algorithms. To this end, we present a new type of multiple tree algorithm that uses a variable number of trees to exploit the advantages of both approaches. We empirically show that this algorithm performs well using both simulated and astronomical data.

Notes

Number of pages: 19

Text Reference

Jeremy Martin Kubica, Joseph Masiero, Andrew Moore, Robert Jedicke, and Andrew J. Connolly, "Variable KD-Tree Algorithms for Efficient Spatial Pattern Search," tech. report CMU-RI-TR-05-43, Robotics Institute, Carnegie Mellon University, September, 2005

BibTeX Reference

@techreport{Kubica_2005_5141,
   author = "Jeremy Martin Kubica and Joseph Masiero and Andrew Moore and Robert Jedicke and Andrew J Connolly",
   title = "Variable KD-Tree Algorithms for Efficient Spatial Pattern Search",
   booktitle = "",
   institution = "Robotics Institute",
   month = "September",
   year = "2005",
   number= "CMU-RI-TR-05-43",
   address= "Pittsburgh, PA",
}

The Robotics Institute

Menu