Search:
Lehrstuhl  |  Institut  |  Fakultät  |  LMU
print


The UST Project
Handling Uncertainty in Spatio-Temporal Data


Overview

UST data
The problem of modeling and managing uncertain data has received a great deal of interest, due to its manifold applications such as information extraction on the web, information integration, scientific databases, sensor data management and entity resolution. With this project we want to transfer the lessons we have learned so far back to one of the origins of uncertain data, namely spatio-temporal and moving objects data. Here uncertainty arises usually from two sources of error:
  • Absence of position information for an entity (e.g. due to non-existent GPS signal)
  • Uncertain position information for an entity (e.g. due to imprecise RFID tracking)

To get a grip of this uncertainty the key idea is to model possible object trajectories by stochastic processes, which has several major advantages over previous approaches.


Goals

Within this project we aim to study and find solutions for the following subtasks:

  • Appropriate models for Uncertain Spatio-Temporal data (i.e. expressive and efficient)
  • Efficient Query Evaluation
  • Mining UST data
  • Development of a framework for managing UST data

UST Framework

To allow a broader application of the developed techniques we are working on an object oriented C++ implementation of the UST Framework. The implementation is currently in a pre-alpha state. We still hope that it helps other researchers understanding the algorithms, evaluating the techniques and implementing new modules.

Download C++ Code


In an early state of this project we developed a framework in matlab which can also be downloaded but is not as comprehensive as the C++ implementation: Download Matlab Code


Artificial Data

The following video describes the pipeline for generating artificial uncertain spatio-temporal data. The dataset created in this example consists of 10000 states. The average branching factor of the underlying transition matrix is 8, the number of objects is 250, the time horizon of the database is 500. The time interval between two observations is 10.


Publications

PDF Talk Title
T. Bernecker, L. Chen, T. Emrich, H.-P. Kriegel, N. Mamoulis, and A. Züfle.
Managing Uncertain Spatio-Temporal Data.
In Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Querying and Mining Uncertain Spatio-Temporal Data (QUeST), Chicago, Illinois, 2011.
T. Emrich, H.-P. Kriegel, N. Mamoulis, M. Renz, and A. Züfle.
Querying uncertain spatio-temporal data.
In Proceedings of the 28th International Conference on Data Engineering (ICDE), Washington, DC, 2012.
T. Emrich, H.-P. Kriegel, N. Mamoulis, M. Renz, and A. Züfle.
Indexing uncertain spatio-temporal data.
In Proceedings of the 21th ACM International Conference on Information and Knowledge Management (CIKM), Maui, Hawaii, USA, 2012.
J. Niedermayer, A. Züfle, T. Emrich, M. Renz, N. Mamoulis, L. Chen, H.-P. Kriegel.
Similarity Search on Uncertain Spatio-temporal Data.
In Proceedings of the 6th International Conference on Similarity Search and Applications (SISAP), A Coruna, Spain: 43–49, 2013.
J. Niedermayer, A. Züfle, T. Emrich, M. Renz, N. Mamoulis, L. Chen, H.-P. Kriegel.
Probabilistic Nearest Neighbor Queries on Uncertain Moving Object Trajectories.
In Proceedings of the VLDB Endowment (PVLDB), Volume 7(3): 205-216 ,2013.
T. Emrich, H.-P. Kriegel, J. Niedermayer, N. Mamoulis, M. Renz, A. Züfle.
Reverse-Nearest Neighbor Queries on Uncertain Moving Object Trajectories.
In Proceedings of the 19th International Conference on Database Systems for Advanced Applications (DASFAA), Bali, Indonesia: 92-107, 2014.
T. Emrich, M. Franzke, H.-P. Kriegel, J. Niedermayer, M. Renz, A. Züfle.
An Extendable Framework for Managing Uncertain Spatio-Temporal Data.
In Proceedings of the ACM International Conference on Management of Data (SIGMOD), Snowbird, Utah: 1087-1090, 2014.

Talks

Tutorial on Managing Uncertainty in Spatial and Spatio-temporal Data (April 2014)
Given by Andi, Tobi and Goce Trajevski at ICDE 2014
Modelling and Querying Uncertain Spatio- Temporal Data (Janurary 2014)
Given by Tobi at the University of Southern California

Contact

Tobias Emrich, Matthias Renz, Andreas Züfle, Johannes Niedermayer
blank