In this paper we examine the problem of efficiently finding sets of observations that conform to a given underlying motion model. While this problem is often phrased as a tracking problem, where it is called track initiation, it is useful in a variety of tasks where we want to find correspondences or patterns in spatial-temporal data. Unfortunately, this problem often suffers from a combinatorial explosion in the number of potential sets that must be evaluated. We consider the problem with respect to large-scale asteroid observation data, where the goal is to find associations among the observations that correspond to the same underlying asteroid. In this domain, it is vital that we can efficiently extract the underlying associations. We introduce a new methodology for track initiation that exhaustively considers all possible linkages. We then introduce an exact tree-based algorithm for tractably finding all compatible sets of points. Further, we extend this approach to use multiple trees, exploiting structure from several time steps at once. We compare this approach to a standard sequential approach and show how the use of multiple trees can provide a significant benefit.

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.