大规模概率数据的管理与查询优化

Uncertainties are inevitably involved in almost all important decision problems. Examples include noise generated in data measurement, errors produced in parameter estimation, and so on. Generally speaking, one systematic way to deal with uncertain data is to view the data as random variables and to manage and query the data according to probability theory. As the volume of probabilistic data generated increases drastically, handling such data becomes a highly difficult problem. Therefore, we need new database systems and query optimization algorithms to answer the new challenge. Due to its significance and difficulty, building probabilistic databases and developing scalable and efficient query optimization algorithms recently have attracted a lot of attentions from database and algorithm researchers. In this project, we aim to systematically investigate the problems of managing and querying large-scale probabilistic data. In particular, we plan to study the following concrete problems: (1) Developing more efficient algorithms for processing SQL, ranking and range queries for uncertain data; (2) Developing streaming algorithms for uncertain data sets; (3) Studing various optimization problems under uncertain input; (4)Identifing new applications for probabilistic databases, especially in new application domains such as wireless sensor data monitoring and crowdsourcing.

几乎所有的决策问题都不可避免的包含了一定程度的非确定因素，如数据测量中产生的噪音，参数估计的误差等等。一般来讲，处理非确定性数据的一个系统的方法是将这些数据视为随机变量，然后以概率论为原则去进行数据处理和优化。随着生成的非确定数据的规模日益增加，处理和查询这些数据的难度也越来越大。因此我们需要新型的处理随机数据的数据库系统和新的查询优化算法。今年来，关于概率数据库和处理随机输入数据的优化算法是国际上研究的热点和难点，存在很多挑战。我们计划在本项目中对随机数据的管理和查询优化算法进行深入系统的研究。具体来讲，我们计划深入探索如下问题：（1）关于非确定数据上的SQL查询，排序，区间查询等问题的更有效的算法；（2）非确定数据的流算法；（3）在非确定输入下的各种优化问题；（4）非确定数据处理算法的应用，特别是在如传感器网络数据监控、群众外包等新兴领域中的应用。

近年来，随着各种信息采集、整合系统，社会网络数据，机器学习预测算法的普遍采用，这些算法和系统所产生的非确定数据，随机数据，概率数据的规模也日益增加。同时，各类决策问题也都不可避免的包含了一定程度的非确定因素。因此，处理和查询这些数据，并基于这些数据来解决优化问题的难度也随之加大。.该项目在这个大的背景下，有步骤的、系统的研究了处理和查询非确定数据，以及随机优化领域的若干问题，并取得了重要进展。其中，有代表性的成果包括（1）在随机组合优化领域，我们发展了泊松近似的技术，并利用该技术给出了一大类随机组合优化问题的最优近似算法，改进了前人在多个相关问题上的结果；（2）在概率模型学习与表示领域，我们第一次给出了最优的学习离散混合模型的采样复杂度；（3）在随机学习算法领域，我们第一次给出了多臂bandit选取问题的最优采样算法。另外我们对于随机数据上区间查询，大规模数据的清洗等问题进行了深入研究并给出了更有效的算法。我们结合了概率论，组合优化，凸几何，泛函分析，矩阵摄动理论，傅立叶分析和函数近似理论等多个领域的思想和工具，提出了处理随机数据，学习概率模型，以及解决随机优化问题的若干新技术，并利用这些技术解决了若干该领域内重要理论问题。在项目支持下，我们还在相关领域如近似算法、最近邻查询算法以及网络算法方面取得了若干成果。.在该项目支持下共发表会议与期刊文章 22 篇，其中 CCF A 类会议及期刊文章 8 篇，包括计算机科学顶级会议及期刊STOC，SODA，VLDB，NIPS，ICML，PAMI，TON等。