Probabilistic Query Processing in Uncertain Spatio-temporal Data

• Applicant: Professor Dr. Matthias Renz
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2013 to 2017
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 240143479

With the wide availability of satellite, RFID, GPS, and sensor technologies, spatio-temporal data - data incorporating both location and time information - can be collected in a massive scale. Datasets containing such information are therefore becoming increasingly large, rich, complex, and ubiquitous. The efficient management of such data is of great interest in a plethora of application domains. However, due to physical limitations of sensing devices and the time-discrete nature of measurements, such data is inherently imprecise.The goal of this project is to investigate efficient and effective methods for modelling, querying and analyzing uncertain spatio-temporal data. In this project, we envision to develop query methods that are able to maximize the reliability of query and analysis results. This aim can be reached by trying to incorporate the complete information that can be extracted from potential uncertain spatio-temporal data into the query process. Thereby, the complexity of the description of the inherent uncertainty, the incorporation of dependencies between entities as well as coping with huge amount of data are the most critical challenges. We try to cope with these problems by using stochastic processes to model uncertain movement of objects in space. Based on such models, we plan to develop first algorithms and techniques to support efficiently the most important spatio-temporal query predicates in a probabilistic way, such as range queries, nearest-neighbor queries and intersection queries. Our main challenge is to return possible results associated with the corresponding probabilities of being a result. The results can then be returned to the user, sorted in descending order by their probability value, giving the user important information about the reliability of the returned results. In addition, data mining solutions, such as clustering and pattern mining for uncertain spatio-temporal data will be investigated. Here, too, we want to directly incorporate models for uncertainty in order to return results with an associated grade of confidence.We plan to reach these goals by applying analytical methods to obtain algorithms to compute the probability based on the uncertainty model. In cases where analytical methods fail due to computational complexity, we will research numeric approaches to approximate the result probabilities, while giving guarantees on the quality of these approximations.

• DFG Programme: Research Grants