基于略图挖掘的在不同时空域的网络流式数据实时处理

In recent decades, with the rapid development of sensor technology and computer networks, an unprecedented amount of data have been collected from all corners of the world. In order to realize the real-time processing of collected data, researchers have defined the concept of "data stream", which is an ordered sequence of data items. For an arbitrary data stream, it is required to examine by only one pass, using only limited storage space for information encoding and decoding. Data stream technology, due to its high processing efficiency and low memory cost, has been adopted by numerous real-world applications, such as traffic measurement in high-speed networks and data compression for wireless sensor networks. However, existing streaming algorithms mainly focus on real-time mining of a single data stream. As far as we know, they are still inadequate with regards to simultaneous processing of multiple input streams, especially when streams are generated in different temporal and spatial domains. Therefore, the goal of our project is to develop techniques that enables the mining of multiple data streams (at different times and locations) for complex temporal and spatial semantic information. Specifically speaking, we will develop a package of algorithms that serves the following three purposes: (1) from a huge number of data streams, extract their aggregate knowledge efficiently; (2) analyze the correlation between data stream records at different time periods; (3) coordinate the functioning of stream processing engines at different locations, in order to construct summary for distributed streaming data. Benefiting from these achievements, we are going to build an algorithm library for distributed stream processing, and use real network data traces to verify the correctness and effectiveness of our proposed algorithms.

近年来随着计算机网络和传感器技术的发展，人们从世界各个角落采集数据，带来了数据规模的飞速增长。为了满足人们对实时数据处理的需要，学者们提出了流式数据：它是数据的一个序列，并且要求在处理过程中任何元素只能读取一次，以及只能利用空间受限的高速存储介质。流式数据处理在实际系统得到广泛的应用，比如骨干网流量分析、无线电子标签监测、搜索引擎数据分析等等。然而，现有的算法主要关注单个数据流的实时分析，在海量数据流的并行处理以及多时空数据流的关联分析方面仍然不够深入和完善。为此，本课题拟对时空域的流式处理的关键技术和理论进行深入研究。在符合应用需求的前提下，设计一套分布式的流式数据实时处理机制及算法，包括海量数据流聚合信息挖掘、不同时间段的数据流的关联分析和模式识别、不同空间域的数据流处理节点的协同工作。基于上述阶段性研究成果，申请人将研制流式数据处理算法库，并实际验证所提出方法的正确性和有效性。

随着软件定义网络和数据中心网的快速发展，基于流式数据处理方法的网络流量测量成为研究热点，可以为网络故障诊断和网络异常检测提供基础测度数据。此外，随着无源传感网的发展，无线射频标签RFID技术逐步普及，物流仓储系统中的大量射频标签的高效估算和管理成为近年的另一个研究热点。然而，传统的网络测量技术和RFID标签集合估算技术无法实现高精度、低开销、近实时的估算测度数据估算，也无法有效支持跨时空域的联合数据分析。本报告研究了如何改进和利用基于略图挖掘的流式数据处理方法实现上述目标。..具体来说，在本项目的资助下，我们分别研究了如下的科学问题。（1）单数据流的存储空间紧凑的基数近似估算问题：我们的算法空间需求比最新的HyperLogLog数据流基数估算法压缩20%-50%。在Hacker News上，我们的算法成为最受欢迎的HyperLogLog算法改进之一，并被英国的Axiom Inc.公司实现和用来分析时序数据。（2）海量数据流并发输入时的大基数流估算问题：申请人所提出的基数估量器，已被用于分析来自CAIDA的真实网络流量数据，相对传统估算法将空间要求降低十倍。该论文算法的实现代码被世界领先的键值内存数据库Redis和时序数据库Influx接收成为标准模块之一，用于检测top-k的大基数流。（3）两个RFID标签集合的联合估算问题：我们额外利用了射频标签间的无线信号冲突信息，将两个标签集合的交并补规模估算在达到预设精度的前提下，将协议执行的时间成本降低35%。（4）RFID标签集合扫描的时间长度自适应调整算法和双标签集合的联合估算问题：我们自适应调整每个标签集合扫描的帧长度，允许利用不同长度的帧扫描数据，推断出两个标签集合交并补的规模。这与传统的固定帧长度的标签集合扫描算法相比，达到同样估算精度的时间成本降低了数倍。（5）任意多个RFID标签集合的联合估算问题：我们研究如何准确估算任意多个RFID标签集合的交并补运算结果的基数。我们的算法兼容RFID标准协议EPC C1G2，且允许帧长度的自适应调整。相比于以前的多集合联合估算法，我们的算法将各个标签集合的扫描时间减少了数倍。..截止目前，我们项目的研究成果是6篇第一作者SCI/EI论文，其中发表了在中国计算机学会CCF的计算机网络方向A类期刊论文四篇，在A类会议论文一篇，和B类会议论文一篇。