大规模流数据的在线摘要方法研究

Big data in practice is usually presented as large-scale and high-speed streaming data. Its large volume and high velocity have posed burdens for efficiently managing and processing data. Meanwhile, streaming data usually contains noisy and redundant data, which wastes a lot of computation resources of traditional streaming data processing systems. To address this issue, we propose a set of streaming data summarization techniques that can reduce the size of big data significantly, and also reduce the complexity of subsequent computation. We study two types of streaming data: one is the common data streams, and the other is the graph streams. 1) For common data streams, we propose an efficient online data summarization technique, which enjoys a constant approximation factor. 2) For graph streams, we propose an efficient core nodes tracking algorithm, which also enjoys a constant approximation factor. 3) For graph streams, we design a compact graph sketch data structure, which supports accurate graph query and computation tasks; meanwhile, we propose an efficient graph sketch updating algorithm. Our streaming data summarization techniques can be widely applied in the area including streaming data management, network data analysis, network security, and so on.

大数据在实际应用中经常呈现为大规模高速流数据，给数据管理和处理带来极大挑战。由于流数据中噪声及冗余数据的存在，会使得通过扩展计算能力来提高流数据处理效率的传统流数据处理方式产生计算资源浪费的问题。为解决这一问题，本项目研究一种通过对大数据“瘦身”从而降低后续计算复杂度的流数据在线摘要技术。本项目研究两类流数据：一般数据流和图数据流。1）针对一般数据流，本项目设计一种低复杂度的数据流在线最优摘要算法，证明算法存在常数近似比例。2）针对图数据流，本项目设计一种低复杂度的关键节点在线跟踪算法，证明算法存在常数近似比例。3）针对图数据流，本项目设计一种紧凑的图梗概数据结构，可以支持常用的图查询与图计算操作，并满足精度要求；同时设计一种低复杂度的图梗概结构更新算法。本项目的研究成果可以在流数据管理、网络大数据分析及网络安全监控等方面产生应用。

大数据在实际应用中经常呈现为大规模高速流式数据，给数据管理和计算带来极大挑战。本项目提出开展大规模流式数据在线摘要方法研究，通过对大数据构建梗概摘要（Sketch）结构、子集选择等运算，从而实现去除大数据冗余内容、抽取大数据关键信息，达到降低大数据管理和计算的复杂度的目的。项目团队着重针对两类流式数据开展了研究，分别为一般数据流和图数据流。针对一般数据流，项目团队提出了几种低复杂度的数据流在线摘要算法，可以高效生成当前流式数据紧凑的梗概摘要结构，通过分析该梗概摘要可以实现对原始一般数据流的在线分析，包括基数计数、在线优化等等。针对图数据流，项目团队提出了几种高效的图数据流在线计算方法，可以高效的对图数据流进行子图频数统计，以及进行关键节点在线跟踪。项目团队对以上所提方法进行了深入理论分析：对于估计类问题，项目团队的研究成果可以给出所设计方法的估计误差情况；对于优化类问题，项目团队的研究成果可以从理论上证明近似解与最优解的可用性之间存在常数倍近似比例。本项目的研究成果可以在流式数据库设计、网络大数据分析及网络安全监控等方面产生应用。项目团队经过三年的研究工作，已经在 ACM SIGKDD、IEEE ICDE、IEEE TKDE 等国际知名会议和期刊上发表论文 8 篇，另外有 2 篇期刊和会议论文在审；已申请发明专利 2 项，其中 1 项进入实质性审查阶段；已获得软件著作权 1 项；培养博士生 1 名，硕士生 3 名。.