图流近似处理研究

任何收存和保管本论文各种版本的单位和个人，未经将本论文转借他人，亦不得随意复制、抄录、拍照或以任何I图流是一个由不断到达的数据项组成的序列，每一个数据项表示两个点之间的一条边。这些数据项组成了一个持续变化的动态图。图流在社交网络、网络测量、网络安全等领域都有广泛应用。图流的更新速度快，数据规模大，这使得对其进行精确的存储与查询十分困难。相比之下，代价更小的近似算法更受青睐。本文以图流近似处首先，本文提出了适用于滑动窗口模型的数据流摘要算法框架Slidingsketch。图流是广义数据流的一种，也就是随着时间不断到达的数据项组成的序列。数据流中的些数据流查询的摘要算法，它们虽然存在一定的误差，但是具有高更新速度和低空间一般是最新的数据，过于老旧的数据会被认为过期失效。因此，实际应用中需要能够其适用于最常用的数据老化模型——滑动窗口模型。该框架可以应用于多种已有摘要算法，使它们支持滑动窗口模型。通过将其应用于不同的摘要算法，Slidingsketch可以支持包括存在性查询、频率查询、高频项查询在内的多种查询。实验表明，Sliding数据项查询的数据流摘要算法，图流摘要算法可以支持复杂的面向图结构的查询。目前的图流摘要算法中，能同时支持多种图查询的摘要算法大多基于点和边的聚合。它是这类摘要算法处理更新的速度很慢，不足以满足图流高速更新的需求。而另一类算法则是通过哈希方法将图流中的点进行聚合，将图流压缩为更小的摘要图并存储。这类算法虽然更新速度快且空间占用可控，但是查询准确率较低。本文提出了一种新的图流摘要算法GSS，其属于哈希聚合的摘要算法，但是设计了独创的紧凑数据结构保存哈希压缩后的摘要图。相比已有的摘要算法，GSS可以在相同的空间内保存更大的摘要图，从而取得更高的查询精确度。此外，GSS通过支持边查询、一跳前驱查询和一跳后继查询三种基本查询算子，实现了对多种图查询的支持，并且能够支持高速的边增删。实验证明GSS的空间占用可以达到经典图存储方法邻接链表的30更新速度可以达到邻接链表的141倍以上，且在多种查询中具有远高于已有摘要算法最后，本文以三角形计数为例研究图流上的近似持续查询算法，设计了滑动窗口要算法的主要目的是以小空间、高速度存储图流数据，在查询时，则需要在存储数据上运行各种查询算法得到结果，这带来了一定的响应时延。而持续查询算法则能在图流更新过程中实时维护查询结果。由于图查询的复杂性，精确的持续查询算法往往需要大量的空间消耗，并且处理更新的速度有限。作为替代，近似查询算法则以较小的可控误差为代价，取得了更小的空间占用和更快的更新速度。其中的一类代表性算法便是三角形近似计数算法。图流上的三角形近似计数算法大多以采样算法为核心。通过采样技术抽取部分边，构造出一个较小的样本图，根据实时维护的样本图上的三角形数目，实现对图流中三角形数目的实时估算。大部分现有工作假设图流中不存在重复边，而且边不会过期。然而在实际应用中，图流中的边往往会重复出现，而且图流数据也需要进行老化，删除老旧的数据以避免影响新近数据的分析。因此，本文设计了一种同时支持重复边和滑动窗口的三角形近似计数算法SWTC，其具有限定大小的空间消耗，而且支持多种三角形计数语义，如二项计数、带权计数、全局计数和局部计数。实验表明SWTC相比简单的固定概率采样方案和通过组合已有技术实总结来说，本文围绕图流近似处理，由浅入深展开研究。本文从图流的近似存储算法入手，首先研究了支持简单的数据项查询的数据流摘要算法，之后又进一步研究了支持复杂的图结构查询的图流摘要算法。为了提高查询时效性，本文又以三角形近似计数为例研究了图流上的近似持续查询算法。本文在这些问题上提出了多个原创算ApproximateGraphStreamProcessingXiangyangGou(ComputerAABSTRACTAgraphstreamisacontinuoussequeriesindatastreams,likequeriesaboutpfdataitems,arealsoimportantingraphsmembershipquery,frequencyquertheSlidingsketchhashigheraccuracAmongexistinggraphstreamsketches,thosewithareusuallybasedongroupingnusage,theiraccuracyispoor.Thisrshcompression.ComparedtopriorwhenprocessingedgeinsertionsanddeletimuchhigheraccuracythanpriorartofgraphstrAtlast,thispaperusesappimatealgorithmsforcontinuousqueries,andproposesaspeedandsmallmemoryusage.Theyneedtocarryoutquemarizeddatawhenquerying.Thereforeittakestimebeforethequhighmemoryconsumptionheseapproximatealgorithms,aptrepresentativekinds.Approximatetrianglecountingalgorithmsingrapsamplegraph.Thentheymaintainanapproximationofthetriabasedonthissamplegraph.ofrecentdata.Therefore,thispaperproposesanalgorithmforapproximatetriaVboundedmemoryconsumptionandsupportsmultipletrianglecountingcounting,weightedcounting,localcountingandglobalcounting.thatSWTChasahigheraccuracythanthebaselinemethod,whichisacombinationofffaroundthesetopics,andexperimentalresultsconfirmtheirsuperioritycomparKEYWORDS:Graph,GraphStream,D 3.1数据流摘要通用模型 3.5.1支持存在性查询的算法: 3.5.2支持频率查询的算法: 5.2.3滑动窗口内互异边数目的估计 X 6.1.2基于哈希聚合的图流摘要算法 3.1数据流摘要实验中使用的算法的缩写 4.5GSS在SSSP查询中的平均相 3.5存在性查询的错误率 3.6支持存在性查询的摘要的更新速度 3.7频率查询的平均相对误差 3.8支持频率查询的摘要的更新速度 3.9高频项查询的错误率 3.10高频项查询的平均相对误差 3.11支持高频项查询的摘要的更新速度 4.2哈希函数值域大小对算子正确率的影响 4.4使用平方哈希后的GSS矩阵结构 4.6异构图流处理系统架构 4.8一跳前驱查询准确率 4.9一跳后继查询准确率 5.2基准方案的算法框架 5.7不同种类的有向三角形 5.10精确度随滑动窗口长度的变化 5.11精确度随样本率的变化 5.12精确度随重复边比例的变化 5.13有向三角形类型A估算效果 5.14有向三角形类型B估算效果 5.15局部三角形估算 5.16带权计数估算效果 5.17不同算法的处理速度 1组，表示两个实体之间的关联关系。根据是否区分边的方向，图可以分为有向图和无向图两大类，图1.1分别展示了有向图和无向图的示意图。由于图结构同时包含了实体的属性信息和实体之间的复杂联系，大量不同的查询可以在图结构上进行，例如可v3v3v1v1v2v5v5v5v5v4v4v2/v4v3/有向图无向图近年来，随着信息技术的不断发展，图数据的规模和实时性都不断增加，图流得到了愈发广泛的关注。图流是一个持续不断到达的数据项序列，序列中的每一个数据项都代表了图中的一条边。这个数据项序列组成了一个持续不断变化的动态图。图流在互联网环境中具有广泛的应用，下面列举几个应用示例。1.一个社交网络中的所有用户组成了一个点集合，而用户之间的发送信息，点赞等互动则组成了一个持续到达的边序列，从而形成了一个图流数据集。该图流形成了表示用户间交互的动态图。在该动态图上可以通过计数三角形进行社区2.互联网中的IP地址组成了一个点集合，而IP之间的数据包通信则组成了持续到达的边序列，它们一起组成了一个图流数据集。在这样的图流数据集中，可23.电商平台上的用户和商家组成了一个点集合，而交易行为则组成了一个不断到达的边序列，其中的每一条边代表一个用户在一个商家处完成了一次购买，该边序列组成了一个图流数据集，并构成了表示电商交易数据的动态图。在此动态图上可以进行子图匹配来发现刷单行为，通过环路检测来发现可能的洗钱活1.更新速度快：图流中数据到达的速度非常高，在大型社交网络和数据中心，图流数据的吞吐量可以高达每秒数万甚至数十万[14]。这要求数据结构和算法能够2.数据规模大：图流数据组成的动态图可以有数亿条边。例如在twitter上，每天有超过一亿用户登录，超过5亿tweet被发布1，这些tweet在被转发或评论时3.查询复杂度高：图流形成的图具有复杂的拓扑结构，在其上进行的查询具有多项式级[1,9]甚至指数级[7-8]的复杂度，在高速更新的场景下对这些查询的支4.单轮实时处理：每当一条边到达时，需要根据已到达的数据对该边进行实时处理，例如持续查询问题中需要根据新边实时更新查询结果，而在图采样算法中则需要实时决定新边是否被采样。此外，算法只能在图流数据的一轮到达中对在图流场景下，数据存储和查询都面临着新的挑战：从存储的角度看，图流同时具有图和数据流两方面的特性，二者的存储方法在图流场景下都有应用，但也都有不Row，稀疏行压缩)等形式。这些结构能够同时保存图中的点和边的信息,以及图的拓扑结构，从而支持各种复杂的图查询，但是，它们在图流场景下空间和时间效率却不尽人意。邻接矩阵的存储空间是o(|V|2)的，|V|为图流中点集合的大小，而其他两个数据结构的存储空间都是o(|E|)的，|E|为图流中边集合的大小。在应用中，大规模图往往十分稀疏，也就是说点集合的规模十分巨大，这使得邻接矩阵o(|V|2)的复杂o(|V|)的,在更新速度较高的图流场景，这样的更新速度并不令人满意。此外，很多1https://www.websitehostingratin3情况下，图流处理需要在资源紧张的嵌入式设备环境下进行，例如在路由器或者交换一些研究工作设计了将图数据进行摘要存储以压缩空间占用的方案[15-17]。但是，这些另一方面，传统的数据流存储方案则侧重于对于独立数据项的存储和查询，并追求高空间效率和高更新速度。经典数据结构如哈希表及其各种变体[18-19]、平衡二叉搜索树[20]等可以用于保存数据流中的数据项，而通过引入可控误差来获取更高时间和空间效率的摘要方案[21-23]也得到了广泛的研究。使用这些数据流摘要方案来对图流中的点或者边信息保存时，可以达到线性（o(|E|或者o(|v|)）的空间占用以及常数级外的复杂查询。虽然研究者们近年也提出了一些专门为图流设计的摘要方案[24-25]，但是它们或者更新速度较低，或者在查询时具有较高的误差。综上所述，图流数据的存储问题依然上文这些存储算法在图流数据到达的过程中不断更新数据存储，而当需要回答查询时，则在当前存储的数据上运行静态图查询算法得到结果。因此查询需要一定的响应时间。而在一些应用中需要实现持续查询，也就在图流数据项不断到达情况下实时或者任意时刻都能立刻报告答案的目的。这使得本已较为复杂的图查询变得更有挑战性。在这样的图流查询算法研究中，除了精确查询的算法外[26-28]，研究者们也提出了一些近似查询的算法[29-30]。这些近似算法通过引入一部分的误差来提升处理图流更新本文的研究从存储方法和查询算法两方面展开，分别研究数据流和图流上的摘要本文将以图流数据近似处理为核心，由浅入深，从三个方面展开研究。首先，本边的信息存储。虽然目前已有多种数据流摘要算法，但是这些摘要算法大多不支持数据老化机制。本文设计了一种数据流摘要算法框架，其能够应用于多种已有数据流摘要算法，使它们支持经典数据老化模型——滑动窗口模型。通过应用于不同的摘要算法，该框架可以支持多种经典数据流查询，并取得高精确度。上述数据流摘要算法虽4然能够保存图流中点和边的信息，但是却不能保存图的拓扑结构，不能支持前驱/查询，路径查询等更复杂的查询。因此，第四章进一步研究了图流摘要算法GSS，该一种基于采样的近似三角形计数算法SWTC。该算法支持对图流中的三角形数目的持续查询，也就是随着图流更新实时维护三角形数目的估算值。相比已有三角形近似计数算法，该算法可以应用于更加复杂的真实场景，支持重复边以及滑动窗口模型，并例如给定一条边，查询边在图流中是否存在，或者找到作为边源点出现频率最高的一批点。这些查询虽然简单，但是却在网络安全[31-32]等领域着重要的应用。举例来说，互联网的通信数据组成了一个图流，其中每一个点代表了一个IP，一条扑结构，所以可以将每个数据项独立存储。这时图流被作为更广泛意义上的数据流看比使用哈希表等精确数据结构，这些摘要算法的空间占用更小，可以保存入cache等然而，目前存在的大部分数据流摘要算法只能处理单增模型，也就是只能处理数据项的添加，不能支持数据项的删除或者老化。而在现代图流应用中，很多场景需要删除过于老旧的数据，而只关注最新的数据。例如在网络安全领域，管理者更希望发现新近发生的黑客攻击以进行阻止，而对很久之前的攻击的关注度则较低。这种情况在数据老化模型里，最常见的模型为滑动窗口模型。该模型使用一个窗口，只将最近一段时间内到达的数据项包含在内，并将其视为有效。而窗口之外的数据则是无效的过期数据。摘要算法若希望支持该模型，一般需要设计机制去删除窗口外的数据。目前已有的支持滑动窗口的数据流摘要算法包括ForgetfulBloomfilter[34]、ECM等。然而，这些算法在处理滑动窗口模型时，因为无法及时删除所有的过期数据，会在第三章中，本文设计了一种处理滑动窗口模型的数据流摘要算法框架Slidingsketch。该框架可以应用于多种已有的，不支持滑动窗口模型的摘要算法，如Bloom5filter和CMsketch，并使它们支持滑动窗口模型。精确删除所有过期数据需要保存窗因此处理滑动窗口模型的算法一般都选择保存一个接近于滑动窗口的数据流片段。但是如何让这个片段足够接近滑动窗口是一个严苛的挑战。为了解决这一挑战。Slidingsketch利用了已有的一类摘要算法的相似点。这些摘要算法都将每个数据项使用哈希函数映射到多个存储位置，在其中保存多份相关信息，在查询时返回其中最准确的一个。Slidingsketch通过使用异步老化的机制，让每个数据项的不同映射位置保存不同数据流片段内的信息，最终实现任何时刻查询时，总有一个映射位置保存了一个足够通过应用于不同的摘要算法，Slidingsketch可以支持包括存在性查询，频率查询和高频项查询在内的多种查询。实验结果表明Slidingsketch在上述的数据流摘要算法只能回答图流中的点和边信息查询，但是没有保存图的拓扑结构，不能回答例如路径查询等更复杂的图结构查询。进一步的，在第四章本文研目前已有的图流摘要算法可以分为两类，其中一类是基于数据抽取的摘要算法，它们从图流中抽取部分数据保存，每种摘要只能支持特定的查询。另一类则是将点和聚合类摘要算法可以进一步细分为两类，一类寻找拓扑结构上相似的点进行合并以实在第四章中，本文设计了一种具有高更新速度、高空间效率，支持多种查询，并图流中的多个点可能会得到相同的哈希值，这些点会被映射到摘要图中的同一个点。与这些点相连的边也会被聚合。通过设置哈希函数值域，GSS可以控制压缩后的摘要6这使得它可以使用相同的空间保存更大的摘要图，以达到更高的精确度。该数据结构还具有极高的更新效率，可以满足图流数据高速更新的需求。本文还进一步提出了核上述图流摘要算法虽然可以支持多种查询，但是这些查询需要在摘要数据上运行静态图查询算法得到结果，从发起查询到得到结果需要一定的响应时间。而一些应用需要持续查询，也就是在图流更新的过程中实时维护特定查询的查询结果。例如在电商场景中，需要持续维护图流中的环路集合以发现可能的洗钱行为[36]。这样的场景需要专门为图流设计的持续查询算法。由于图查询复杂度高，同时很多图流处理都需要在资源紧张的嵌入式设备上进行，除了精确的持续查询算法，空间占用更低，计算代价更小的近似查询算法也得到了广泛的关注[29-30]。在近似持续查询算法中，最具有代表性的一类研究便是近似三角形计数算法。三角形计数在社区发现[37]、话题检测[38]和异常检测[39]等领域都有着广泛应用。在这些应用中，三角形的数目不需要完全精确，一定的误差是可以接受的。此外，相比其他查询，三角形计数问题更容易通过采样方法来估算，也就是从图流中采样出一部分的边组成一个较小的样本图，并以样本图中的三角形数目为依据来估算图流中的三角形数目。这使得基于采样的三角形近似计数一直是近年来的研究热点之一。本文以图流虽然基于采样的图流三角形近似计数问题已经有多项研究工作[30,40]。但是这些研究工作往往假设一个十分理想的场景：图中的边不会被删除，而且同一条边不会重复出现。在实际应用中，情况往往复杂的多。图流中的数据可能需要被老化，同一条边也可能在图流中多次出现。例如在社交网络中，每一个用户是一个点，两个用户之间的一次交互是一条边，用户交互数据组成了一个高速更新的图流。由于两个用户之间会多次交互，所以图流中存在重复边。在这样的社交网络中进行话题检测时，近期的热门话题价值更高，所以过去的数据需要被老化掉。而在数据老化的模型中，最常见的是滑动窗口模型。因此，本文希望设计一种支持滑动窗口模型和重复边的三角形近7counting即只考虑互异三角形的数目，以及带权计数（weightedcou重复边组成不同的三角形。本文希望算法同时支持两种查询语义。目前已有的摘要算法在该场景下都有各自的问题，一些工作不能处理边删除[41-42]，还有一些工作则会受到重复边的干扰，不能支持二项计数[30,43]。此外，本文希望算法的空间消耗具有限定大小，而不是随着图流的流量不受限制地变化，以防止在资源紧张的应用中超出预留在第五章中，本文设计了一种基于采样的三角形近似计数方法，SWTC（Sliding似计数，而且具有限定大小的空间消耗。SWTC算法同时支持二项计数和带权计数两和局部三角形计数（localcounting即计数整个图流中的三角形，或者三角形。SWTC使用了一种独创的滑动窗口模型下生成无偏样本图的方法。该方法基于定长切片(fixed-lengthslicing即选取一系列的固定时间点，将图流切分为连续的长度相同的片段，通过片段组合来实现对滑动窗口的查询。SWTC算法融合了定长切片和优先级采样，从而设计出了具有限定空间消耗的无偏采样的方案。基于定长切片的方案，本文也设计出了一种估算滑动窗口内边数的方法，并以样本图中的三角形数目和滑动窗口内的边数为依据，估计滑动窗口内的三角形数目。本文也对SWTC了一系列的改进方案，包括避免速度低谷的计数预测方案和稳定精确度的分组异步采样方案。SWTC是第一个满足本文设计要求的三角形近似计数方法。实验表明SWTC近似存储领域。第三章的研究工作为滑动窗口模型下支持数据项查询的数据流摘要算法，第四章的研究工作则进一步结合了图流中的拓扑结构信息，设计了图流数据专用的摘要算法。这两项工作的主要目的是以高更新速度和高空间效率存储数据，对查询的时效性要求不高。而第三项工作（第五章）则属于图流上的近似持续查询算法。该工作在图流不断更新的过程中持续维护三角形数目的估算值，在任意时刻都能实时报本文研究了图流数据的近似存储和近似查询算法，分别从数据流摘要算法，图流1.本文研究了支持独立数据项查询的数据流摘要算法，设计了在滑动窗口模型下8哈希表哈希表邻接链表二叉搜索树二叉搜索树邻接矩阵数据流摘要算法支持图结构查询图流摘要算法（第四章）精确子图匹配精确子图匹配精确正则路径查询近似三角形计数近似频繁子图挖掘精确算法近似算法数据存储持续查询图流处理其支持滑动窗口模型。通过将该框架应用于不同的摘要算法，Slidingsketch可以支持图流中边和点的存在性查询、频率查询和高频项查询等。而且，通过应用独创的异步老化的机制，Slidingsketch以较低的代价实现了对滑动窗口模型2.本文研究了支持图结构查询的图流摘要方法，设计了图流摘要算法GSS，GSS首先基于哈希方法将原图流压缩为一个较小的摘要图，然后设计紧凑数据结构对摘要图进行存储。GSS具有高更新速度和高空间效率，且同时支持图流上的3.本文研究了图流上的近似持续查询算法，设计了滑动窗口模型下，面向有重复算法基于持续维护的无偏样本图，能够支持图流中全局和局部的三角形数目的持续查询。该算法基于定长切片方案，具有限定大小的空间占用，而且能够同本论文在的结构如下：第二章将介绍相关研究现状，包括本文研究中使用的数据模型定义，问题定义和相关工作简介。第三章将介绍滑动窗口模型下的数据流摘要框架Slidingsketch，第四章将介绍基于哈希聚合的图流摘要算法GSS，第五章将介绍滑动窗口模型下，面向有重复边的图流的三角形近似计数算法SWTC。最后，第六章将9本章将给出本文中使用的数据模型和问题的正式定义，并简要介绍这些问题相关项可以是任意形式的数据。在实际应用中，数据流一般是从数据源持续接收的，例如从互联网上收到的网络包或者社交网络服务器收到的用户通讯记录。现代应用中的数据流具有更新速度快，数据规模大的特点，此外，对于数据流中的数据项的处理需要按照其到达顺序实时进行，而且处理时没有被保存的数据项将在之后丢失，因此算法图流是数据流和图结合而产生的数据模型。图流一般被定义为一个有持续到达的个点同时到达的还有它的完整的邻居列表。第一种模型被称边流：边流模型下，图流为一个持续不断到达的数据项序列S={e1,e2,e3ex},点流：点流模型下，图流为一个持续不断到达的数据项序列S={u络、电商数据等示例中，图流都被维护为边流模型，大部分的图流研究[25,30,44]也使用了边流模型。只有少数以图流划分算法为主的相关工作中[45-46]中使用了点流模型。本t1t2t3t4v2v1v1v2↓v4!v3v3v3v1!v4!v5v5v5v2点流t1v1v4t2v1v2t3v3v1t4v2v3t5v3v4边流t6v3v5t7v5v2图流中不断到达的数据项组成了一个持续不断变化的动态图。图2.1中的两种形与一般的数据流相比，图流不仅同样具有更新速度快，数据规模大，需要单轮实时处理的特点，同时还结合了图数据的复杂性。数据流中的数据项被认为是互相独立的，而图流中的边却通过共同的端点互相关联，最终形成了复杂的图结构，而在这样的图结构上，可以进行的查询也更加多样，复杂度也更高，这使得对图流数据的存储举例来说，社交网络分析可能只关心最近的用户交互，因为用户的社交行为在不断变在这种情况下时，可以使用滑动窗口模型。滑动窗口模型分为基于时间的滑动窗基于时间的滑动窗口：一个长度为N的滑动窗口包含所有时间戳在(T-N,T]范在实际应用中，基于时间的滑动窗口更加常见也更加复杂。基于计数的滑动窗口可以看作是一种简化的基于时间的滑动窗口，也就是每一个时间单元内有且只有一条图流在滑动窗口模型下导出的动态图中只包含在滑动窗口内的边，滑动窗口之外的边被认为失效。随着时间推移，滑动窗口内会不断有新边加入和旧边被删除，从而导致其形成的的动态图不断发生变化。图2.2展示了滑动窗口和t7时刻滑动窗口中的边组成的动态图的示例。本文用W−N表示T时刻长度为N的滑动窗口。更一般地，t1v1v4Wt2t3t4t5t6t7v1v2v3v1v2v3v3v4v3v5v5v2v5v2v4v3一些应用会明确地给出指示，删除之前到达的数据项。例如在电商数据中，可以的一条边。同一条边可以在图流中的不同时刻被多次加入或者删除。多次加入可视作同一条边的多个副本，而每一个删除项ei=(u,U,−,ti)在不特殊指明的情况下，表示滑动窗口模型也可以应用在含删除的图流上。当使用了滑动窗口模型时，删除项注意显式删除和滑动窗口模型有所不同，显式删除中，每一个数据项的删除是通过图流中数据项指明的，删除已有的数据项的顺序可以是任意的。而在滑动窗口模型中，数据项的删除是隐式的，随着时间的流逝旧的数据项会自发地过期，这样的过期事件需要算法自身去发现，而数据项过期的顺序是固定的。这样的区别使得处理显式删除模型和滑动窗口模型的算法难以通用。将显式删除模型的算法用于滑动窗口模型时，可能需要额外的数据结构去维护数据项的时间顺序，以确定每一个数据项过期的时刻。而滑动窗口模型的算法可能由于不能处理任意顺序的删除而无法用于显式删除本节对本文研究的问题给出定义，并介绍不同问题的已有研究工作。首先，2.2.1节将介绍数据流上的常见查询和摘要算法，并介绍本文研究的关注重点，滑动窗口下的数据流摘要的已有算法。因为图流自身是数据流的一种，这些数据流摘要算法也可以应用于图流中，对图流上的边和点的频率等属性进行存储和查询。但是当以更复杂图结构查询为目标时，需要更加复杂的存储结构，2.2.2节将介绍常见的精确图存储结构，这些存储结构为之后的图流近似存储奠定了基础。2.2.3节和2.2.4节将进一步介绍图和图流的摘要算法，相比精确存储结构，这些摘要算法虽然可能引入误差，但具有更低的空间消耗，可以用来存储大规模图数据。最后，2.2.5节关注图流上的持续查图流是数据流的一类，数据流中的一些常见查询在图流中同样重要。本文重点研究三种数据流基本查询：存在性查询、频率查询和高频项查询。下文将分别介绍这些有在它们全为1时才给出肯定回答，否则便给出否定回答。Bloomfil即使数据项不在数据集中，它也有概率给出肯定回答。后续行了多种改进以使其支持不同的场景，例如Bloomierfilter[21][22]CMsketch由一个被均分为k段的计数器数组组成。所有的计数器都被初始化为说报告出的结果只会比真实结果高，不会比真实结果低。CUsketc有和CMsketch相似的数据结构，但是不同的更新策略。它们具有更小的误差，但是包括Pyramidsketch[53]、Augmentedsketch[一些应用只关心频率较高的数据项，例如在网络异常检查中，发出IP包数目大，也就是作为边源点出现频率高的IP较为可疑。高频项查询便是找出频率较高的数据项的查询。根据对“高频率”的定义方法的不同，高频项查询可以分为Top-K查询和heavyhitter查询两种语义。Top-K查询为找出频率最大的K个数据项，而heavyhitter查询则为找出频率超出一个给定阈值的查询。大部分支持高频项查询的摘要同时支持两种查询。由于heavyhitter查询的频率阈值在应用中难以确定，Top-K查询使用得更虽然上一节介绍的频率查询摘要也能应用于高频项查询，但是专门为高频项查询设计的摘要算法通过牺牲对于低频项的支持获得了更小的空间占用。当前最好的高频项查询摘要算法是HeavyKeeper[58]。它对于数据流中的数据项频率提供查询支持，并且为高频项的查询结果给出精确度保证。它使用一个被称为指数衰减（count-而在高频项查询中达到了高精确度。其他的高频项查询算法包括Frequent[59]、Lossycounting[60]、Space-Saving[3通，在滑动窗口模型下，即使是支持显式删除的算法需要辅助数据结构来按时序保存滑动窗口内的所有数据项。这样的辅助数据结构消耗的空间远大于摘要算法自身。因本文根据支持的查询，将滑动窗口模型下的摘要算法分为三类：第一类是支持存在性查询的算法，这些算法一般是在Bloomfilter上增加不同的改进机制以适应滑动窗口。例如，ForgetfulBloomfilter[34]用多个Bloomfilter来记录不要，这些数据流片段和滑动窗口相交，可以使用这些片段的摘要来实现对于滑动窗口filter[63]等。第二类是支持频率查询的摘要算法，这类算法一般以CMsketch为基础进行改进，如ECM（ExponentialCout-Min）sketch[35]将CMsketch数组的每一个位置从计数器更换为一个指数直方图（ExponentialHistogram[64]指数直方图是一种用于滑动窗口中数据项数目估算的数据结构，ECMsketch用每一个位置的指数直方图来估算映射到该位置的数据项在滑动窗口中的频率，并结合CMsketch的更新和查询机制来支持有精确度保证的频率查询。其他的相关工作包括SplitterWindowedCount-Min数据项设置一个窗口计数器（windowcounter该结构包含一个频率计数器以及一个时间戳队列，每当该数据项在数据流中到达时便增加频率计数器，频率计数器的值达到特定阈值时将其清空，并在队列中记录到达阈值的时刻。之后，算法可以根据队列中时间戳的数量和计数器值来计算数据项的总频率。通过定期清理滑动窗口外的时间戳记录，可以实现对于过期数据的删除，而通过对所有数据项的windowcounter进行衰减,则可以在内存达到可用上限时去除低频项，保持空间占用可控。Hung等人[69]结合了WindowCounter和数据流切片方案，提高了算法的更新速度，而之后的Window目前已有的滑动窗口模型下的数据流摘要算法大多只能应用于特定的查询，不具有通用性。此外，它们为了支持滑动窗口模型引入的改进机制仍然会消耗大量的存储资源，导致其在可用空间较小时精度不佳。本文的第三章将利用已有摘要算法的共同特点，提出一种摘要算法框架，其可以应用于多种已有的摘要算法，使它们支持滑动窗口模型，并且通过应用于不同的摘要算法，可以支持存在性查询、频率查询和高频数据流摘要算法具有更新速度高、空间占用小的优点，可以保存在高速度，小容成数据缓存[71-72]和cache控制[73-75]等功能，也可以在存储资源紧张的嵌入式环境，如路由器上部署，从而节省宝贵的存储空间,完成IP查找[76-77]和异常检测[78]等。在图流场景下，这些数据流摘要算法可以用于保存图流中的点和边的信息，从而支持对于点和边的高速查询。但是，当需要支持图拓扑结构相关的查询时。便要使用专门为图设计的，更加复杂的存储结构。下文将分别介绍精确图存储结构，图摘要算法，和已有对于图数据的存储方式已经有了大量研究。最常见的精确图存储数据结构包括邻其他位置则被填充0。邻接矩阵只需要o(1)的时间便能定位到一条边，对其进行修改或查询。通过进行行扫描或者列扫描，邻接矩阵还可以支持o(|V|)时间内的点前驱/后继查询。但是邻接矩阵存储图的空间代价为o(|V|×|V|),实际应用中的大规模稀疏图常常具有百万甚至千万以上的点，这种情况下上述空间代价是不可接受的，这也限邻接链表是另一种常见的图存储结构，它使用一个点表存放图中的所有点。点表中的每个点具有一个后继链表，以单链表的形式来存储自己的后继邻居。而如果要在图上进行前驱查询，还需要额外为每一个点建立一个前驱链表。在邻接链表中，存储空间代价为o(|E|),相比邻接矩阵，这一空间代价即使在存储大规模图数据时也是可以被接受的。但是邻接链表查找或修改一条边的代价则为与边源点的度数，也就是源接链表查找或修改一条边的代价是o(|V|)的。在大规模图中，很多点的度数十分高。这使得边更新的代价较为高昂。除此之外，邻接链表还可以通过定位到查询点并读取前驱/后继链表的形式来进行点前驱/后继查询，时间代价依的图流应用和系统都以邻接链表为基础[79-80]。邻接链表的空间消耗虽然已经是o(|E|)的，但是大量指针的使用使其仍会占用较多的内存，此外，使用链表形式保存邻居使得同一个点的邻居在存储上并不连续，缺加明显。CSR则改善了这一问题。它使用一个点表存储所有点，同时使用一个连续的边表存储全部的边。每一个点发出的边在边表中占据一段连续的区域，在其中存储边的后继点，且同一个点的邻边可以按照后继点的ID排序存储。点表中的每一个点存储有自己的邻边集合的末尾在边表中的偏移量，结合点表中上一个点的偏移量，便可以定位出该点的邻边集合的起始和结束，从而找到所有的邻边。与邻接链表相同，当同时要进行前驱和后继查询时，还需要另外一个边表存储每个点的前驱集合。与邻接链表相比，CSR中没有使用指针，且每个点的邻居连续存储，因此具有更小的空间消耗和更好的局部性。通过对每个点的后继进行排序存储，CSR还可以使用二分查找在O(log(|V|))的时间内定位到一条边。CSR进行前驱/后继查询时的时间代价也保持在O(|V|)。但是CSR无法支持边的添当图数据规模过大，或者存储资源紧张时，可以选择使用摘要算法来进一步压缩数据，节省存储空间。目前已有的静态图摘要算法可以分为三类，基于数据聚合的方基于聚合的图摘要算法在图中寻找拓扑结构上相似的点或者边，将它们聚合为超点(supernode)和超边(superedge)来实现图压缩。例如，Fan等人[17]针对不同查询设计了不同的函数来聚合在该查询上等价的点，以实现对该查询无误差的图摘要。Raghavan等人[81]为网络图提出了一个双层的压缩表示，其中低层为若干较小的有向图，每个有向图描述了一组网页及它们之间的关联，而高层则为一个超点和超边组成的有向图，每一个超点代表了低层的一个有向图，超边则描述了这些网页组之间的关联。Riondato等人[82]则在图摘要和代数聚类算法之间建立了联系，设计了一种高效且误差可控的基于点聚合的图摘要算法。其他相关工作还包括发掘紧密连接的点簇并聚合的算法[83-84]和聚合高度数点周围相似边的算法[85-86]。基于抽取的图摘要算法则关注特定的查询，并且通过抽取和这些查询相关的图数证给出的近似解不超过两点间真实距离的k倍。Sp了被称为sparsifier的结构，可以为边割集计算提供近似解。其点或者边过滤的图可视化的方法[87-88]等。比特压缩的方法则通过点和边的重排序以及压缩编码方式来达到压缩存储的目的。例如GBASE[89]中先将图中点根据拓扑相似性划分为多个子集，使得每两个点集之间的连接尽量同质化，也就是两个点集中的点的连接或者特别密集，或者特别稀疏，之后使用zipblock编码对每两个点集之间的邻接矩阵进行压缩编码。Apostolico等人[90]则使用宽度优先搜索顺序对图中点进行排序，从而保证有边相连的两点之间的序号尽可能接近，而序号相邻的点的邻居集合也尽量相近，之后使用增量编码的方式对所有点的邻居列表进行编码以压缩空间。其他工作包括利用社交网络和网页链接的特性对点集进行排序并压缩编码的方案[91-93]以及对边进行重排序和压缩编码的方案[94]等[95-96]。相比静态图摘要算法，图流摘要算法需要支持对摘要的动态更新，上述三类静态图摘要算法中，基于比特压缩的方案不适用于动态更新的场景。因此图流摘要算法主要分为基于抽取和基于聚合的两大类。基于数据抽取的摘要算法在图流场景下已有多篇研究工作，例如在图流上抽取部分数据以构建spanner和sparsifier[97-98],估算最大匹基于聚合的图流摘要算法又可以进一步分为两大类，第一类以MoSSo[24]为代表，这类算法挖掘图流中具有相似邻居集合的点，将它们合并为超点以压缩存储。通过存储修正集，也就是记录压缩后的图和原图相比的差异部分，它们可以做到无损压缩。但是，寻找具有相似邻居的点较为费时，而且在图流更新过程中，点的聚合结果可能第二类算法以TCM[25]为代表，这类算法基于哈希聚合，也就是通过哈希算法对点和边进行合并。它们虽然具有较高的更新速度和可控的空间占用，但是查询误差较的点和边将被聚合，被聚合的边权重将被加和。经过哈希映射，图流将被压缩为一个更小的摘要图，图2.3展示了一个摘要图产生的示例。之后，TCM选择使用邻接矩阵为图流数据是实时到达的，无法提前预知最终的映射情况，因此TCM需要一个大小然而，如上文所述，邻接矩阵在保存大规模稀疏图时的空间效率十分低下。为了将空 多个不同哈希函数产生多份摘要，在查询时从多个摘要的查询结果中选择最准确的一份报告，但是它在涉及图拓扑结构的查询，如点的前驱和后继查询中，依然具有很大t7t8t1t2t3t4t5t7t8v2v3v3v5v1v1vv2v3v3v5v1v1v112v4v2v311112311112v3v4v4vv3v4v4v5v2v1v1v13vv412111v21v23vv366v1,5v2,4v1,5v2,42424vv3度较低的问题。本文的第四章将提出图流摘要算法GSS，它使用了和TCM相似的方法产生摘要图，但是设计了更加紧凑的数据结构来保存摘要图，因此能够在相同空间上文主要介绍了图流的近似存储方法。而图流上的近似查询算法今年来也得到了广泛的关注。这些算法的目标查询往往具有较高的复杂度，并且需要支持持续查询，数[30,42]等。这些算法大多从图流中抽取部分和查询相关的数据并保存，从而为特定查图流上的三角形计数问题即为持续监视在任意时刻图流中的三角形数目。由于定义三角形时并不考虑边的方向，所以三角形计数问题一般将图流形成的动态图考虑为无向图，并且不考虑权重等属性。图流中边是否能重复出现，在不同的工作中有不同的定义，一些算法[40,105]假设图流中没有重复边，而另一些工作[30,42]则假设图流中一条边可以出现多次。当图流中存在重复边时，对于重复边的处理方法也分为带权计数(weightedcounting)和二项计数(binarycounting)两种。具体来说，在图流中的三角形互异三角形的权重和作为结果。图2.4展示了一个三角形计数的示例。图中每条边上1v1v21v1v1v21v3v1v1v1v21v3v5v21v3v51312v4v4v31从另一个角度来看，二项计数可以被看作在去除重复边的图流中进行的三角形计数，而带权计数则是将重复出现的边视作不同的平行边，使其生成复数的三角形。举重复边，而在带权计数中，重复边和互异边对计数结果具有相同的贡献。因此，不考虑重复边的算法一般也可以经过少许改进后应用在带权计数中，而二项计数则需要更常检测[39]等[106-109]都是以此问题为基础的。已经证明图上的三角形计数问题的复杂度是O(|E|1.5),其中|E|表示图上的边数。由于此复杂此往往以近似三角形计数算法[110-112]作为替代，这些算法一般使用采样算法，从图中抽取出一部分边，维护一个小规模的样本图，在样本图中计数三角形，然后再计算原图中每一个三角形被采样到样本中的概率，从而根据样本中三角形的数目，计算出原近年来在图流上进行三角形计数的算法包括MASCOT[113]，一种使用固定概率独立采样图流中的每一条边，并同时估算局部和全局三角形的算法，以及Pavan等人的基于邻居采样的三角形计数算法[40]、Jha等人的基于双边采样的三角形计数算法[105]、Ahmed等人提出的适用于图流的通用图采样方案[114]等。然而上述这些算法并不考虑用了被称为蓄水池采样[115]的方案并且具有固定大小的空间消耗。通过使用被称为随机配对（randompairing）[116]的方案，它也实现了对显式边删除的支持。此外，它也支持含重复边图流中的带权计数。但是一方面它不能过滤掉重复边，因此不能支持二项计数。另一方面，TRIST可以处理显式删除，也就是说它需要被明确告知每一条边的删除。然而滑动窗口中的边的删除是隐式的，随着时间推移，旧的边会自动过期。把TRIST应用于滑动窗口模型时，需要用额外空间完整保存滑动窗口内所有边的时序，以确保能及时发现所有过期边，并对其调用删除函数，这样才能保证样本集无偏。然而，保存滑动窗口内所有边所需的空间代价比算法本身维护样本图的代价要高出数倍作PartitionCT[42]通过过滤掉重复边来在图流中实现二项三角形计数。它使用哈希函数将图流切分为若干个子流。在每一个子流中，它使用另一个哈希函数来进行优先级采样（prioritysampling并从每一个子流中选出一条边组成样本图。PartitionCT也通过结合计算出的边优先级和StreamingHyperloglog算法[117]实现了对图流内互异边数目的估计，从而计算出每条边被采样的概率，实现从样本图中三角形数目到图流中三角形它们或者不支持边删除，或者不支持二项计数，而且正如上文所说，即使是支持显示删除的算法，在滑动窗口模型下效果也不理想。据本文作者所知，目前没有限定空间消耗的，滑动窗口模型下的含重复边图流中的三角形近似计数方法。因此，本文的研究目标之一，便是提出适用于滑动窗口模型 SeTG=(V,E)Ww2时刻到达的数据项组成的集合wNw−NGsGhlnewloldH(·)MmdkAFXBtestR(·)在图流数据上可以进行的最简单的查询是不涉及图拓扑结构的，对于点和边等独立数据项的查询，例如查询某条边在图流中是否出现、某个点出现的频率等。这时图流可以作为数据流进行摘要和查询。数据流中的数据项可以是图流中的边，也可以是图流中每条边的源点或者目的点。关于数据流摘要的算法已经得到了多年的研究，相比精确存储算法，这些摘要算法具有更小的空间占用，可以存入cache等更小更快的存储结构，或者在资源紧张的嵌入式设备中使用。然而，支持数据老化机制，如滑动窗口模型的摘要算法目前仍十分稀少。本章将提出滑动窗口模型下的数据流摘要框架它们可以被应用于滑动窗口模型。通过应用于不同的摘要算法，Slidingsketch可以支本节首先介绍一种数据流摘要的通用模型，k-hash模型，许多经典的数据流摘要数据结构:k-hash模型的数据结构如图3.1所示。它由一个等分为k段的数组组eAh1(x)h2(x)h3(x)h4(x)A口映射格子用一个查询策略stq根据k个格子保存的信息计算出查询结果。不同摘要的查询策略使用CMsketch举例：不同摘要算法的更新和查询策略不同，下面以CMsketch计数器都增加1，因此一个数据项的频率被累加到了它映射到的每一个格子上。而它的查询策略则是报告k个映射格子中计数器的最小值，因为每一个映射格子的值都是映射到它的数据项的频率和，所以该值不小于被查询的数据项的真实频率，而且k个Slidingsketch可以应用于所有符合k-hingsketch用在一种摘要算法时，本文称改进前的算法为基础摘要，改进后的算法用个槽，A[i][0]和A[i][1]，每一个槽是一个和基础摘要相同的数据结构，如比特或者计更新：当一个新的数据项e到达时，Slidingsketch使i<k}将其映射到k个位置{A[hi]|0≤i<k}，每段一个（也就是说hi(·)是在子的A[hi][0]槽。扫描：扫描操作用于删除过期数据。Slidingsketch使用一个扫描指针匀速重复扫描数组A。每当指针扫描到数组结尾时，它返回数组开头并开始新一轮扫描。扫描数指针每个时间单元内扫描个格子。每当指针扫描到一个格子时路标时刻。在一个格子的路标时刻，Slidingsketch删除A[i][1]中的值，将A[i][0]的值赋给A[i][1]，并将A[i][0]清空。查询:查询一个数据项e时，Slidingsketch找到它映射的k个格子{A[hi]|0≤i<k}。在每一个格子里，Slidingsketch算法把两个槽的值求和，最终得到k个和CMsketch找到k个映射的格子后，把每个格子两个槽中的值加和，最终找到k个和中这些序列把整个数据流分为了若干等长的片段。每个片段可以比喻为一天，而不同的每一个格子的两个槽位分别记录了该格子在最近两个片段内收到的信息。而在一个数据项映射到的k个格子中，路标序列的偏差导致了保存信息的时间异步，而Slidingsketch能保证总有一个格子里保存的信息足够接近滑动窗口内的信息。下一节中会对由于扫描操作，每一个格子A[i]具有一个路标时刻序列{lj|j=0,1,2....}对任意正整数j≥0，有lj+1−lj=N，这些路标将整个数据流切分成了若干等长片段{w+1|j=0,1,2....}。假设对于当前时刻有lt<T≤lt+1，下文设Slidingsketch用槽A[i][0]保存在当前片段中被映射到格子A[i]的数据项的信作为对滑动窗口内映射到格子A[i]的数据项信图3.2展示了一个格子A[i]的路标序列对图流进行片段切分的示例，当前片段为片段3，时差为，滑动窗口包含了当前的片段3和片段2的后。而片段3加片段2T=14滑动窗口(N=6)t=1t=3t=4t=5t=6t=7t=9t=11t=12e1e2e3e4e5e6e7e8e9e10e113片段1片段2片段3061218在每一个格子A[i]中，A[i][0]+A[i][1]存储了一个长度为N+δN个时间单元的数去估算滑动窗口中数据项信息的误差便越小。由于扫描指针匀速扫描整个数组，δ的值取决于格子和扫描指针之间的距离。假设这些格子中的时差足够小，可以保证估算精度。准确来说，可以证明一个数据项e总有一个映射格子A[hj1]使得0。详细推导会在3.4节中给出。段中的频率，加上哈希冲突（多个数据项映射到一个格子）带来的误差。当数组中的格子数足够大时，哈希冲突带来的误差可以被控制在较低的水平，对滑动窗口进行近似带来的误差是估算误差的主要组成部分。由于CMsketch的查询策略会选择最小的上一节假设数组每一个格子被分为2个槽位，更一般的情况下，Slidingsketch在每个格子中使用d(d≥2)个槽位{A[i][j]|0≤j<d}。这些槽位记录了最近d个片段内映射到该格子的数据项的信息。如果假设当前片段为wtt+1，那么槽位A[i][j]记录的是片段wtt+1中的信息。在这种情况下，应当有lj+1−lj=也就说每个片段是i<k}，数组每段一个。之后使用基础摘置A[i][j]=A[i][j−1](1≤j<d)，A[i][0]=0。i<k}，然后计算k个和{sum(A[hi])=ΣA[hi][j]|0≤i<k}，最后将基础摘要的是说每一个片段是滑动窗口长度的。当前片段为片段5，时差为，滑动窗口和片段T=14滑动窗口(N=6)t=1t=3t=4t=5t=6t=7t=9t=11t=12t=13e1e2e3e4e5e6e7e8e9e10e11片段1片段2片段3片段4片段503691215当使用多槽位时，Slidingsketch的精确度可能会提高个片段都是滑动窗口长度的，所以这d个片段的和是滑动窗口长度的来精度提升，因为内存占用不变的情况下，增加每个格子的槽位数目也意味着格子数目的降低，哈希冲突带来的误差会提升。槽位数目和格子数组之间的权衡根据基准算的哈希函数来完成地址计算，但是k个哈希函数有一定的计算代价，为了进一步降低4.a,b,都比p小。之后使用g2(e)作为一个偏移量计算出映射地址{hi(e)=(ri(e)+g2(e))%+i× 机序列，而即使两个数据项e和e′出现了g1(e)=g1(e′)，只要g2(e)≠g2(e′)，映射地址序列依然不会相同。而g1(e)=g1(e′)且g2(e)=g实验结果表明，使用伪随机算法可以在不影响精确度的情况下把Slidingsketch水和低能耗的优势。一块FPGA加速板由一个FPGA芯片和数块板上内存组成。每一存占用大部分情况下很小，应用中可以尝试将其放在FPGA上实现Slidingske来数组中的每一个格子被变形为矩阵的一列了便利扫描操作的进行。FPGA在一次存储访问中可以读写64字节的每一个槽位小于4字节，所以，在扫描操作中可以一起操作多个相邻列，也就是同格子更新和查询操作可以同时使用并行和流水加速。一次更新操作可以并行访问数据项在矩阵不同段的映射格子，完成对它们的更新。查询操作也可以并行读取不同映射格子中的值，然后再把得到的值进行比较以选出最终结果。此外，一批更新或者查询操作可以进行流水线加速，也就是把更新/查询函数在芯片上的执行逻辑分为若干单该单元。如此可以实现两个更新/查询操作间隔的时钟周期数小于完成一次更新/查询需要的周期数，从而提高操作吞吐量。两个操作之间的间隔被称为启动间隔II。在最理想的情况下启动间隔可以为1个时钟周期。Slidingsketch的查询操作可以达到该间因此，启动间隔等于完成更新所需的时钟周期数。3.6.7节中的实验表明，使用FPGA本节对Slidingsketch的性能给出分析。3.4.1节将Slidingsketch的空间复杂度是O(md),m是数组的格子数目而d是每个格子的槽位数目。在应用中，m的长度一般和滑动窗口长度线性相关，而sketch算法中，每一个数组格子被分为d个槽位，每个槽位的数据结构都和基础摘要Slidingsketch每个槽位中的数据结构要比基础摘要简单。例如HeavyKeeper的每个格一个格子仍然只记录一个数据项的ID，而d个槽位在最近d个片段内的频率。这种情况下SlidingHeavyKeeper的内更新算子的时间复杂度是O(k)的，因为其需要找到k个格子，但在每一个格子中只更新一个槽位。而查询算子的复杂度是O(kd)的，因为其需要找到数据项映射的k个格子，在每一个格子中需要计算d个槽位的和（注意在FPGA加速方案中，由于对于数组中的每个格子A[i]，其时差δ表示了当前片段的长度相比完整片段长度的比例，可以根据格子和扫描指针之间的距离计算。假设一个格子在矩阵中的序号为1)hj1<q时，A[hj1]拥有所有映射位置中最小的时差。q−hj1小于数组一段的长这种情况下k个映射格子中最大的时差出现在相邻的下一段中，假设这一段中的格子为A[hj2]，也就是说j2=(j1+1)%k。因为hj2−q小于