Variable KD-Tree Algorithms for Efficient Spatial Pattern Search

Jeremy Martin Kubica, Joseph Masiero, Andrew Moore, Robert Jedicke, and Andrew J. Connolly
tech. report CMU-RI-TR-05-43, Robotics Institute, Carnegie Mellon University, September, 2005


Download
  • Adobe portable document format (pdf) (4MB)
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",
}