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

Jeremy Martin Kubica
doctoral dissertation, tech. report CMU-RI-TR-06-01, Robotics Institute, Carnegie Mellon University, December, 2005


Download
  • Adobe portable document format (pdf) (7MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
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? 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.

Notes
Associated Lab(s) / Group(s): Auton Lab
Associated Project(s): Auton Project
Number of pages: 200

Text Reference
Jeremy Martin Kubica, "Efficient Discovery of Spatial Associations and Structure with Application to Asteroid Tracking," doctoral dissertation, tech. report CMU-RI-TR-06-01, Robotics Institute, Carnegie Mellon University, December, 2005

BibTeX Reference
@phdthesis{Kubica_2005_5554,
   author = "Jeremy Martin Kubica",
   title = "Efficient Discovery of Spatial Associations and Structure with Application to Asteroid Tracking",
   booktitle = "",
   school = "Robotics Institute, Carnegie Mellon University",
   month = "December",
   year = "2005",
   number= "CMU-RI-TR-06-01",
   address= "Pittsburgh, PA",
}