Servicenavigation

Project Details

Back

Projekt Print View

Probabilistic Query Processing in Uncertain Spatio-temporal Data

Subject Area Security and Dependability, Operating-, Communication- and Distributed Systems
Term from 2013 to 2017
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 240143479
 
Final Report Year 2018

Final Report Abstract

The primary goal of the project was to develop and evaluate solutions for efficient management, query processing and analysis of spatio-temporal data in consideration of the inherent uncertainty of such data. In this project, we mainly addressed the two key problems, modelling and representing of uncertain spatio-temporal data (Subproject 1) and efficient and effective approaches for querying and analyzing uncertain spatio-temporal data (Subproject 2). To address the first problem, we developed a framework that enables us to further study and to obtain a deeper intuition of the quality of spatio-temporal data models. Based on this framework, we could show the applicability and quality of discrete Markov chain models for the modelling of uncertain spatio-temporal data based on artificial and real world trajectory datasets. With the assumption of mutually independent objects (object trajectories), our experimental results show that the Markov chain model is a promising and sufficiently accurate approach providing efficient ways of inference required for expensive probabilistic query processes. In contrast to traditional models for uncertain spatiotemporal data using spatial extrapolation techniques based on spatio-temporal constraints, such as maximal speed, direction, etc., our Markov-chain model is able to preserve spatial and temporal dependencies and, thus, yield more accurate results without much loss of query performance. However, the drawback of our model is that it needs a set of historic data (observations) to train the model. Though, we conducted our study primarily on road-traffic trajectory data, our approach is also applicable to any spatio-temporal data providing observations of space (incl. any form of multidimensional feature space) and time and, thus, it provides a solution for a wide application field. In our studies on modeling uncertain spatio-temporal data, we additionally addressed the problem of discovering information about the uncertainty inherent in spatio-temporal data. We considered alternative routing approaches based on uncertain routing conditions as well as uncertainty in sets of trajectories that is induced by inconsistent states of trajectory databases. The later approach is based on mutual dependencies between objects, e.g. two trajectories can’t meet at the same place at the same time. Though both approaches yield sets of sets of alternative trajectory instances, we had problems in identifying an appropriate probabilistic model that assigns likelihoods for each of the trajectory instance. Though, due to lack of further knowledge, given a set of alternative trajectories, the assumption of an equal distribution is still best practice to overcome this issue. In the third part of Subproject 1, we focused on methods for representing and computing objects with uncertain spatial extension. In this part of our study, we first focused on the problem of computing Voronoi cells for uncertain data which are useful for a range of spatial and spatio-temporal query processing tasks, including nearest neighbor search and continuous nearest neighbor search. The main challenges we addressed here were 1) the identification of models for the representation of uncertain Voronoi cells that are applicable for major application fields and 2) methods for efficient computation of these representations. For the first problem, we introduced the concept of Possible Voronoi cells and Guaranteed Voronoi Cells, both represented by a quadtree-based hierarchical spatial partitioning. With novel spatial pruning techniques we were able to overcome the high computational cost for the computation of these Voronoi cells. Furthermore, we also studied approximate approaches for similarity queries for uncertain spatially extended objects (fuzzy objects) based on shape descriptors. Our results showed that multi-step query processing approaches achieve higher accuracy but less query performance than techniques that approximate distance-confidence potentials by means of Sigmoid functions. In the second part of this project, Subproject 2, we first concentrated on efficient and effective approaches for querying and analyzing uncertain spatio-temporal data. In addition to approaches for efficient probabilistic query processing based on the models and data representations studied in the first part (Subproject 1), including a novel approach for probabilistic reverse nearest neighbor query processing, we also investigated methods for probabilistic continuous monitoring queries on sensor networks with uncertain sensor readings. Specifically, we elaborated solutions for continuous aggregation and fusion of continuously changing values. The key achievement of this study is a new strategy for updating SUM query results efficiently in an incremental way. In addition, toward our investigation on indexing uncertain spatio-temporal data, we studied generalized index methods for multi-represented objects, where we showed how similarity search over multiple metrics can be efficiently supported by one single index structure. One of our main contributions to this project are our studies on pattern mining in uncertain data. Here, we concentrated on clustering problems that are of particular interest for spatio-temporal data in many applications. Due to the requirement of the consideration of inter-object dependencies, analytical approaches become hard problems. To overcome this problem, we investigated approximate solutions based on sampling (Mote-Carlo Sampling). The main idea was a strategy to identify an appropriate small set of significant representations of possible clustering results accompanied with confidence information, respectively. Our approach has shown to be general applicable to several pattern mining and spatial query processing problems and has been integrated in an open-source framework ELKI, that has been well received by many research groups. In the context of sampling-based query processing on uncertain data, we finally studied the problem of maximizing the information flow in uncertain sensor networks. The result of our study is an hybrid of analytic and sampling-based approach that lead to a patent that has been registered with the support of Siemens AG. To conclude, we have contributed many novel algorithms to the rapidly growing market for the data quality and uncertainty aware information retrieval and knowledge discovery in the context of spatial and spatio-temporal data. An important open question emerging from our project is the relevance of the accuracy of probabilistic models for the quality of the results of diverse query processing and pattern mining results.

Publications

 
 

Additional Information

© 2024 DFG Disclaimer / Copyright / Privacy Policy

Textvergrößerung und Kontrastanpassung