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.