Efficient Discovery of Spatial Associations and Structure with Application to Asteroid Tracking

The problem of finding sets of points that conform to a given underlying spatial model is a conceptually simple, but potentially expensive, task that arises in a variety of domains. The goal is simply to find occurrences of known types of spatial structure in the data. However, as we begin to examine large, dense, and noisy data sets the cost of finding such occurrences can increase rapidly. In this thesis I consider the computational issues inherent in extracting model-based spatial associations and structure from large amounts of noisy data. In particular, I discuss the development of new techniques and algorithms that mitigate or eliminate these computational issues. I show that there are several different types of structure in both the data and the problem itself that can often be exploited to this end. Primarily, I describe a new type of tree-based search algorithm that uses a variable number of tree nodes to adapt to both structure in the data and search state itself. While the problem of finding known types of spatial structure arises in a wide range of domains, the primary motivating problem throughout this thesis is the task of asteroid linkage and tracking. Here the goal is to link together individual point observations in order to find and extract new asteroid trajectories in the data. Ultimately, the goal is to identify and track all asteroids that are large enough to penetrate the earth’s atmosphere and cause significant damage upon impact. Future astronomical surveys will provide a wealth of observational data to this end, greatly increasing both the ability to find new objects and the scale of the problem. Thus efficient algorithms are vital to effectively handle the massive amount of data that is expected