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

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

课题研究数据流的分布存储和访问以及连续查询的方法。通过原子概要结构为多个计算提供数据流压缩存储，突破概要结构和计算一一对应的关系，建立它们间的多对多关系，因此，减少数据冗余，节省存储更新时间。在大数据存储和处理的背景下，分别从计算集合的存储和通讯复杂度角度，研究数据流原子概要结构及其维护。. 在概要结构方面的研究集中在两个方面：1）离散结构数据流的均匀样本获取：数据流的数据来自离散空间，在分布环境下由于数据冗余或出现频率等原因导致样本发生偏斜，使得均匀样本的获取变得困难。首先解决了均匀样本获取问题，然后把该采样方法应用于分布数据流上的聚集函数估计和聚类计算；2）复杂结构数据的分割和子图查询：当数据流数据来自于复杂结构空间时，特别是图结构的语义RDF数据时，研究通过视图进行复杂图结构数据的分割、相应的查询分割，然后将查询分割映射到相关的图分割而完成部分查询，最后，通过联接操作完成查询。. 在概要结构维护方面重点研究了分布数据流的k-median聚类结构和一般聚集结构的维护，通过触发函数的凸性有效地控制通讯复杂度。从特例着手，研究分布数据流k-median聚类结构的维护，首先解决有效更新问题，然后解决有效通讯问题。在此基础上，研究一般的聚类问题，统一分布数据流上k-means和k-median聚类结构的维护，并在Twitter’s的STORM平台上实现了分布数据流一般聚类结构的维护。. 在大数据（Big Data）背景下对研究做了些调整和拓展：1）图结构RDF数据流的视图储存技术研究：重点研究了基于视图的图结构数据分割，然后研究相应的查询分割方法，通过数据分割和查询分割的对应关系，将查询导向相关分割。这种分割和查询导向的方法是图结构数据分布存储的基本方法之一；2）拓展研究数据扰动对计算估计的影响，以此阻止非善意的信息获取（阻止隐私泄露）。数据扰动和数据流的概要存储都会对数据产生扭曲，前者侧重通过扭曲阻止针对隐私的估计，后者着重于从扭曲数据中获取精确估计。. 上述研究的成果主要体现在：IEEE ICDE、ACM CIKM等重要国际学术会议论文3篇，包括JCST、FCS的SCI和EI期刊论文10多篇，申请专利2项，参加学术会议和交流6人次，培养研究生10多名.