Probabilistic Query Processing in Uncertain Spatio-temporal Data

随着卫星、RFID、GPS和传感器技术的广泛应用，时空数据（包含位置和时间信息的数据）可以大规模收集。因此，包含这些信息的数据集变得越来越大、丰富、复杂和无处不在。这些数据的有效管理在大量的应用领域中具有很大的意义。然而，由于传感设备的物理限制和测量的时间离散性，这样的数据本质上是不精确的。本项目的目标是研究高效和有效的方法来建模，查询和分析不确定的时空数据。在这个项目中，我们设想开发的查询方法，能够最大限度地提高查询和分析结果的可靠性。这个目标可以通过尝试将完整的信息，可以从潜在的不确定时空数据提取到查询过程中。因此，描述固有不确定性的复杂性，实体之间的依赖关系的合并以及处理大量数据是最关键的挑战。我们试图用随机过程来模拟空间物体的不确定运动来科普这些问题。基于这样的模型，我们计划开发第一个算法和技术，以有效地支持最重要的时空查询谓词的概率方式，如范围查询，最近邻查询和交集查询。我们的主要挑战是返回与结果的相应概率相关联的可能结果。然后可以将结果返回给用户，按其概率值降序排序，为用户提供有关返回结果可靠性的重要信息。此外，数据挖掘解决方案，如聚类和模式挖掘不确定的时空数据将进行研究。在这里，我们也希望直接结合不确定性模型，以便返回具有相关置信度的结果。我们计划通过应用分析方法来获得基于不确定性模型计算概率的算法来实现这些目标。在分析方法由于计算复杂性而失败的情况下，我们将研究数值方法来近似结果概率，同时保证这些近似的质量。

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.