Variable KD-Tree Algorithms for Efficient Spatial Pattern Search
by Jeremy Kubica, Joseph Masiero, Andrew Moore, Robert Jedicke, and Andrew Connolly
BibTeX:
@techreport{kubica_2005_0543,
author = "Jeremy Kubica and Joseph Masiero and Andrew Moore and Robert Jedicke and Andrew 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"
}
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.
- Download PDF