图作为一种可以描述实体间复杂关系的数据结构,在网络异常检测、社交网络分析、道路交通预测等领域都有着广泛应用。传统的批处理方法需要把整个数据结构加载到内存中,这对于日益增长的大规模图数据显然不适用。而流处理只需要有限的内存即可实现对大数据进行实时在线处理,因此面向图流数据的相关算法研究具有重要意义。图流数据中的超点是指图中度大于一定阈值的节点,图中的超点往往具有特别的含义,在网络流量图中可能表示服务器、发起端口扫描的攻击者或者是遭受分布式拒绝服务攻击的主机。对图流数据中的节点Jaccard相似度进行估算,可以用于检测网络节点连接状态的相似性,对网络攻击主机进行同源性分析。因此图流数据中的超点检测和节点相似度估算对于网络安全有重要的研究价值。然而现有的超点检测算法要想达到较高的精度,其占用的内存将会过大,不利于在内存有限的设备上部署;现有的Jaccard相似度估算算法主要是对静态集合以及包含元素增添的数据流的集合的相似度估算,对于有元素删除的完全动态变化的图流数据却无能为力。针对上述问题,本文利用基于内存共享的思想对Hyper Log Log进行改进的算法对图流数据中的超点进行检测,在保证估算精度的前提下,降低了算法的内存消耗;本文还提出一种对图流数据中的节点Jaccard相似度进行估算的算法,可以处理图流元素中元素的删除,同时提高了估算精度。本文的主要贡献如下:（1）对基数估算算法以及超点检测算法进行研究,利用基于寄存器共享的思想对Hyper Log Log进行改进的VHLL（Virtual Hyper Log Log）算法进行超点检测,其内存消耗只有当前算法的1/6。VHLL算法在更新阶段把所有元素随机映射到一个寄存器数组中,在估算阶段从公共的寄存器数组中恢复出一个Hyper Log Log估算器,对所有节点的连接数进行估算,从中找到超过连接数阈值的节点。本文还通过理论分析得出了VHLL算法进行超点检测的估算偏差和方差。（2）对现有的Jaccard相似度估算算法进行研究,分析了相关算法的优缺点,基于Odd Sketch算法提出一种分多层抽样的Odd Sketch算法MROS（Multi-resolution Odd Sketch）。MROS算法通过哈希函数把图流元素映射到相应的比特位,如果出现删除的元素则把该元素对应的比特位进行翻转从而实现元素的删除。MROS分层抽样的思想使得每一层Odd Sketch对于节点度在一定范围内的估算都较为准确,提高了节点Jaccard相似度估算的整体精度。本文通过理论分析证明了MROS估算是无偏估计,给出了估算方差的上界。（3）通过实验对上述改进算法进行评估分析,并且与现有的超点检测算法和Jaccard相似度估算算法进行对比,通过真实数据集验证了本文算法的优越性。同时还基于软件定义网络的思想搭建了面向数据面编程的实验平台,通过Mininet构建虚拟网络拓扑,在实验平台上实现了面向高速图流数据中的超点检测和节点相似度估算算法。