分布原子概要的产生及管理

项目名称： 分布原子概要的产生及管理

项目编号： No.60973023

项目类型： 面上项目

立项/批准年度： 2010

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

项目作者： 崇志宏

作者单位： 东南大学

项目金额： 29万元

中文摘要： 数据流研究的一个基本方法是维护反映数据流聚集信息的概要结构。目前研究采用为特定计算设计特定的概要结构，计算和概要间一对一关系在系统需要并发进行多个计算时暴露出严重的问题：1）概要间存在的信息冗余造成存储浪费；2）隐藏在次线性复杂度背后的大常数因子造成实际应用无法接受的系统开销；3）数据流对信息冗余的概要结构进行连续更新造成的CPU浪费。因此，本课题提出计算集算法复杂度来度量并发计算的复杂度，提出可以在多个计算间共享的细粒度和无信息冗余的原子概要结构。本课题研究内容包括基于计算集复杂度的算法设计和分析，概要集分解为原子概要集以及从原子概要集构建概要集的方法，在分布环境下控制维护原子概要集通讯开销的方法。采用的关键技术有线性组合、递归嵌套、算法简化和算法局部化。通过计算集复杂度，将研究从单个计算优化转到对计算集的优化上，体现了建立在数学基础上的空间、结构和精简表示的研究特色和创新。

中文关键词： 数据流；数据流概要；原子概要；连续查询；复杂度

英文摘要：

英文关键词： Data Streams；Synopsis of Data Streams；Atomic Synopsis；Continuous Query；Complexity