学位论文简介
大体量、高流速的网络流数据对现有的存储和计算系统构成了挑战，给网络状态监控、异常检测等网络管理任务带来了巨大的困难。一方面，网络流数据所生成的数据量超过了存储和计算能力，另一方面，又要求着网络流数据的处理需要“一次遍历”、“有限内存开销”和“高效在线执行”。Sketch作为一种内存开销小、空间高效的紧凑数据结构，具备灵活性和强大功能。寻找一种空间高效、响应迅速且近似有效的紧凑数据结构和算法来表示、查询和分析流数据，成为一种可行的解决方案。
本文探讨两类面向网络流数据的紧凑数据结构和算法的设计，一类是基于哈希映射的紧凑数据结构，另一类是针对流数据是多维数据表示的紧凑数据结构的设计。这些研究为网络流数据的多集合成员查询、特征选择以及子空间近似和异常检测等问题提供算法和理论支持。取得了以下主要创新性研究成果：
（1）针对哈希冲突导致网络流数据在多集合成员查询问题中查询精度低的问题，提出基于Bh序列的多集合成员查询方案。该方案支持流数据的多种复杂操作，同时理论分析了方案查询失败率和误报率。它能提以低空间开销和低内存访问次数实现高精度的查询。
（2）在多指标的海量网络流数据中进行特征选择是一项具有挑战性的任务。提出基于矩阵Sketch的流数据特征选择方法，将数据存储在固定大小的矩阵Sketch中，并构建拉普拉斯矩阵捕获流型信息，提供实时、高效的流数据特征选择。
（3）针对网络流数据中子空间的计算代价大、存储开销高，提出一种子空间近似的张量摘要数据结构，理论推导了它的子空间近似误差和投影误差，并在真实网络流量数据集上验证它的近似子空间能进行高效地异常检测。
（4）针对网络流数据中子空间的计算代价大且难以支持分布式计算的问题，提出张量模型的摘要数据结构和它的分布式异常检测方案，理论证明和实验结果表明，该方案在全量数据的异常检测等价于在摘要数据结构的异常检测，实现了高精度、实时、分布式异常检测方案。
主要学术成果
[1] Shuyu Pei, Jigang Wen, Kun Xie, Gaogang Xie, Kenli Li. On-Line Network Traffic Anomaly Detection Based on Tensor Sketch [J]. IEEE Transactions on Parallel and Distributed Systems (TPDS), 2023,34(12): 3028-3045. (CCF 推荐 A 类期刊，本人第一作者)
[2] Shuyu Pei, Kun Xie, Xin Wang, Gaogang Xie, Kenli Li, Wei Li, Yanbiao Li, Jigang Wen. BhBF: A Bloom Filter Using Bh Sequences for Multi-set Membership Query [J]. ACM Transactions on Knowledge Discovery from Data (TKDD), 2022,16(5): 1-26. (CCF 推荐 B 类期刊，本人第一作者)
[3] Kun Xie, Shuyu pei, Xin Wang, Wen Shi, Gaogang Xie, Kenli Li, Yanbiao Li, Jigang Wen. A Stateful Bloom Filter for Per-flow State Monitoring [J]. IEEE Transactions on Network Science and Engineering (TNSE), 2021,8(3): 1399-1413. (SCI二区, 导师第一作者，本人第二作者)
[4] Linxi Li, Kun Xie, Shuyu Pei, Jigang Wen, Wei Liang, Gaogang Xie, CS-Sketch: Compressive Sensing Enhanced Sketch for Full Traffic Measurement [J]. IEEE Transactions on Network Science and Engineering (TNSE), 2024. (SCI二区, 第三作者)
[5] 基于张量模型的分布式网络异常检测, 湖南省研究生创新项目，2020/06-2021/06，主持，已结题
