Abstract
Technology such as the Global Positing System (GPS) has made tracking moving
entities easy and cheap. As a result there is a large amount of trajectory data
available, and an increasing demand on tools and techniques to analyze such
data. We consider several analysis tasks for trajectory data, and develop
efficient algorithms to perform them automatically. In particular, we study
the following tasks:
•Find a segmentation of a trajectory based on a non-monotone criterion.
•Find hotspots; regions in which the entity spent a large amount of time.
•Find all groups and the grouping structure. A group is a movement pattern in which sufficiently many entities move together during a sufficiently long time interval. In addition to the groups themselves we also find the relation between groups, e.g. a large group came into existence when two smaller groups merged.
•Find a central trajectory: a representative for a set of trajectories.
For each task, we formalize the problem, and analyze its geometric
properties. We use these properties to obtain efficient algorithms to
automatically perform the task at hand. In many cases, we also show that our
analysis is tight, and that our algorithms are optimal.
entities easy and cheap. As a result there is a large amount of trajectory data
available, and an increasing demand on tools and techniques to analyze such
data. We consider several analysis tasks for trajectory data, and develop
efficient algorithms to perform them automatically. In particular, we study
the following tasks:
•Find a segmentation of a trajectory based on a non-monotone criterion.
•Find hotspots; regions in which the entity spent a large amount of time.
•Find all groups and the grouping structure. A group is a movement pattern in which sufficiently many entities move together during a sufficiently long time interval. In addition to the groups themselves we also find the relation between groups, e.g. a large group came into existence when two smaller groups merged.
•Find a central trajectory: a representative for a set of trajectories.
For each task, we formalize the problem, and analyze its geometric
properties. We use these properties to obtain efficient algorithms to
automatically perform the task at hand. In many cases, we also show that our
analysis is tight, and that our algorithms are optimal.
| Original language | English |
|---|---|
| Awarding Institution |
|
| Supervisors/Advisors |
|
| Award date | 29 Jun 2015 |
| Publisher | |
| Print ISBNs | 978-90-393-6349-2 |
| Publication status | Published - 29 Jun 2015 |
Keywords
- theoretical computer science
- computational geometry
- geographic information science
- geometric algorithms
- trajectory
- trajectory analysis
- movement analysis
- collective motion
- segmentation
- hotspot