分布式不确定数据查询处理关键技术研究

项目名称： 分布式不确定数据查询处理关键技术研究

项目编号： No.61472425

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 自动化技术、计算机技术

项目作者： 覃飙

作者单位： 中国人民大学

项目金额： 80万元

中文摘要： 由于现代信息技术的发展，数据分布式地产生、存储和处理成为一种常态。在分布式开放环境下，当数据产生时会不可避免地引入一些模糊、不确定甚至错误，本项目用分布式不确定数据库来管理大数据。在分布式环境下，查询处理的首要任务不是计算结果元组的概率值，而是计算分布式不确定数据的特征值，包括top-k、直方图、高频数据、数据草案和概要等。本项目从新颖的采样策略入手，拟提出高效的算法求出不确定数据的特征值，该算法能够近似线性扩展；接着提出大数据的加速处理策略，典型的方法是高效的归并算法和索引技术。本项目还要研究分布式不确定数据的聚集查询和统计技术；由于针对的是海量数据和开放式环境，增量维护是高效求解特征值的关键技术。最后，研发一个分布式不确定数据库原型系统，对本项目提出的理论和算法进行验证和分析。本项目的工作不仅对分布式不确定数据库查询处理有直接意义，而且对MapReduce和数据库的有机结合有理论指导。

中文关键词： 分布式不确定数据；特征值；查询处理；大数据；MapReduce

英文摘要： Data are often increasingly generated, stored, and processed distributively with the information technology development.Meanwhile, when large amounts of data are generated, fuzzy, uncertainty,and even errors are inherently introduced, especially in a distributed setup. We use distributed uncertain databases to manage such massive data. In distributed data management, the key problem of query is not to compute the probabilities of answer tuples but the eignvalues of the distributed uncertain data. The eignvalues include top-k, histograms, heavy hitters, sketches and synopses, and etc. This project begins with novel sampling method. We plan to introduce efficient algorithms to compute the eignvalues of the distributed data. The algorithm can be scaled up in a linear way. We next propose the method to accelerate processing big data. The typical method is efficient merge and index. This project will study the aggregation and statistics in distribution data. Because of the open world and massive data, incremental maintenance is the main technique to efficiently compute eignvalues. Finally, a distributed probabilistic data management system (DPDMS) prototype is implemented based on the query processing techniques developed in this project. This DPDMS is used to demonstrate our theories and algorithms. The project is not only useful for distributed uncertain database queries but also for combining MapReduce and databases.

英文关键词： distributed uncertain data;eignvalues;query processing;big data;MapReduce