Variable KD-Tree Algorithms for Spatial Pattern Search and Discovery
journal contributionposted on 01.01.2005, 00:00 authored by Jeremy Kubica, Joseph Masiero, Andrew W Moore, Robert Jedicke, Andrew Connolly
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.