Graphics enhanced version of this site

Variable KD-Tree Algorithms for Efficient Spatial Pattern Search
J.M. Kubica, J. Masiero, A. Moore, R. Jedicke, and A.J. Connolly
tech. report CMU-RI-TR-05-43, Robotics Institute, Carnegie Mellon University, September, 2005.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Adobe portable document format (pdf) [4417 KB]
Compressed postscript (ps.gz) [457 KB]

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.

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.

Number of pages: 19

J.M. Kubica, J. Masiero, A. Moore, R. Jedicke, and A.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.

@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",
   institution = "Robotics Institute, Carnegie Mellon University",
   month = "September",
   year = "2005",
   number = "CMU-RI-TR-05-43",
   address = "Pittsburgh, PA"
}