Algorithms for analyzing collections of trajectories
Abstract/Contents
- Abstract
- Large scale collections of trajectory data, such as GPS traces, are becoming widely available, and there are many emerging applications that involve understanding and extracting information from such data. Much of this data is noisy, contains outliers, and has missing parts — raising many difficult statistical, geometric, and algorithmic problems. In this thesis, we study methods to extract structure from such data and to organize the data in a fashion that facilitates further analysis. We start by presenting a data-driven framework for smoothing trajectory data. Our framework, which can be viewed of as a generalization of the classical moving average technique, naturally leads to practical algorithms for various smoothing objectives. The second part of this thesis is about understanding the essential structure underlying the collections of trajectories. This topic is similar in spirit to dimension reduction or manifold learning in classical data analysis. Under reasonable similarity measures, collections of trajectories have significantly different structure than that of traditional data sets. In particular, simplifying assumptions such as the belief that the data lies on a low-dimensional manifold are no longer reasonable. Instead, it is often the case that the underlying space of the trajectories has a one dimensional stratified (or branching) structure. Our goal is then to reconstruct such a branching structure from a collection of input trajectories. Using sampling assumptions modeled after previous geometric reconstruction work in the computational geometry community, we formulate a new algorithm for reconstructing branching structures with guarantees. To make such a structure useful, we study the problem of map matching, which enables the branching structure to be used efficiently as a coordinate system. In particular, we extend recent results for Fréchet distance computation to obtain an algorithm for map matching with respect to the Fréchet distance that runs in near-linear time under reasonable models for the input trajectory and the map, which improves on previous near-quadratic running times. Finally, we also study a version of our reconstruction problem in a more general setting with weaker assumptions and develop an algorithm that is oblivious to ordering information of the individual trajectories in the data set, and even to the embedding of the data. Here, we explore a new model of reconstruction we call "metric reconstruction" that lies somewhere between geometric and topological reconstruction. In this model, we reconstruct the topology and distances of the underlying structure, while being somewhat oblivious to its extrinsic embedding. This algorithm allows the reconstruction of branching structures to be extended to settings where ordering information may not be reliable, or even to more abstract instances where an embedding is not available.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2012 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Chen, Daniel |
|---|---|
| Associated with | Stanford University, Computer Science Department |
| Primary advisor | Guibas, Leonidas J |
| Thesis advisor | Guibas, Leonidas J |
| Thesis advisor | Goel, Ashish |
| Thesis advisor | Roughgarden, Tim |
| Advisor | Goel, Ashish |
| Advisor | Roughgarden, Tim |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Daniel Chen. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2012. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2012 by Daniel Chen
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...