A Multiple Tree Algorithm for the Efficient Association of Asteroid Observations

Abstract

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.