Efficient Discovery of Spatial Associations and Structure

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 compu-tational 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 asteroi