file.pdf (207.22 kB)
Variable KD-Tree Algorithms for Spatial Pattern Search and Discovery
journal contribution
posted on 2005-01-01, 00:00 authored by Jeremy Kubica, Joseph Masiero, Andrew W Moore, Robert Jedicke, Andrew ConnollyIn 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.