1.基于滑动窗口的标签感知图形流草图构建方法，其特征在于，包括以下步骤：

S1、获取带有标签和时间戳的异质图数据流；

S2、根据图数据流中到达项目的时间戳对窗口进行滑动；

所述步骤S2中设定滑动窗口的大小是W时间单位，通过将时间窗口划分为k个子窗口，每个子窗口包含W/k时间单位，在仅保留一个最近子窗口的起始时间tn的基础上可以完成草图的有效滑动，通过比对当前时间t与tn，t≤tn+W/k，则开启一个新的子窗口并剔除最远子窗口，实现子窗口的更新并完成整体窗口的滑动；

S3、确定图数据流中的任一项目在矩阵中的存储位置；

所述步骤S3中针对处理的异质图数据流，假定当前到达图数据流的项目表示为e＝(A，B，lA，lB，le，w，t)，其中A和B为项目的两个顶点标识符，lA和lB是顶点对应的顶点标签，le是项目的边缘标签，w是项目的权重，t是项目的时间戳，标识项目到达图数据流的时间；首先利用项目的两个顶点标签lA和lB信息确定其所属的初始矩阵块，然后提取项目本身的标识符A和B作为信息在选定的矩阵块中游走，最终确定其在矩阵中的存储位置，并使用双计数器机制高效记录其到达的边缘标签及对应权重；

3.1、根据顶点标签确定项目所属的矩阵块；

为了高效存储项目的顶点标签，使用矩阵分块思想，将具有相同顶点标签的项目聚集存储在同一个大块中，在不增加存储耗费的基础上完成顶点标签的嵌入，基于预先设置好的草图参数，包括矩阵宽度d、矩阵块宽度b，根据项目的两个顶点标签lA和lB得到对应的哈希值为H(lA)和H(lB)，进而将其转化为二维矩阵中每一维的定位标志H(lA)％m、H(lB)％m，其中m是一维中分块的数量，表示为d/b；由此，可以确定项目所属的矩阵块，该矩阵块的起始位置为(b*H(lA)％m，b*H(lB)％m)，该矩阵块的大小范围为：

A∈(b*H(lA)％m，b*H(lA)％m+b)

B∈(b*H(lB)％m，b*H(lB)％m+b)

3.2、根据标识符信息确定项目所属的矩阵格；

对项目的标识符A和B处理，得到哈希值以及对应的初始地址和指纹，分别为H(A)、H(B)；f(A)＝H(A)％F、f(B)＝H(B)％F，其中F是设定的指纹长度，

根据已有的线性同余方法，使用标识符A和B的指纹f(A)、f(B)作为种子，使用公式



分别生成项目对应的地址候选序列{s1(A)，s2(A)，...，sr(A)}、{s1(B)，s2(B)，...，sr(B)}，其中0≤si(A)≤b,0≤si(B)≤b，r是候选列表的长度，乘数T、增量I、模数M都是线性同余方程中的设定常量，依次检查候选列表并在项目选定的矩阵块中进行游走；若没有冲突，则完成项目在矩阵中的定位；

3.3、使用双计数器机制，存储项目的边缘标签及对应权重；

设计双计数器机制解决图数据流中同一项目多次以不同权重、不同边缘标签到达的统一性问题，定义数量计数器列表C＝{C1，C2，...，Ck}存储项目在不同时间窗口内的所有边缘的总体权重，此外，预定义一个质数列表PList＝{2，3，5，...}，使用哈希函数将每一个边缘标签映射到独有的质数上，利用质数乘积的因式分解的唯一性定义标签计数器列表P＝{P1，P2，...，Pk}，通过将多个时间点到达的具有不同权重、不同边缘标签的项目转化成质数，并乘入计数器列表P，从而在能够分解的情况下高效完成边缘标签的存储；

S4、对矩阵中存在冲突的项目使用额外池进行存储；

S5、融合存储矩阵和额外池两个部分，完成草图的最终构建。

2.如权利要求1所述的基于滑动窗口的标签感知图形流草图构建方法，其特征在于，所述步骤S1中图数据流数据集的预整理，按照时间戳顺序，依次处理图数据流中的项目。

3.如权利要求1所述的基于滑动窗口的标签感知图形流草图构建方法，其特征在于，所述步骤S3包括，

3.1、利用基础的哈希技术和矩阵分块思想，根据项目的顶点标签定位其所在的矩阵块；

3.2、使用线性同余方法生成地址的候选列表，若没有冲突，则完成项目的定位过程；

3.3、使用双计数器机制，存储项目的边缘标签及对应权重。

4.如权利要求1所述的基于滑动窗口的标签感知图形流草图构建方法，其特征在于，所述步骤S4包括，

4.1、根据顶点的标识符确定所属链表；

4.2、使用双计数器机制，存储项目的边缘标签及对应权重。

5.如权利要求4所述的基于滑动窗口的标签感知图形流草图构建方法，其特征在于，所述步骤4.1中根据计算出的项目的顶点标识符的哈希结果H(A)、H(B)，通过对比H(A)找到以A为起始节点的单一链表，遍历该单一链表，若某一结点的存储内容为H(B)，则完成定位；否则，需要在该链表的尾部新增存储内容为H(B)的结点。

6.如权利要求1所述的基于滑动窗口的标签感知图形流草图构建方法，其特征在于，还包括步骤S6，通过查询，完成对图数据流的分析。

7.基于滑动窗口的标签感知图形流草图构建方法的应用，其特征在于，将该方法应用于交通网络，对图数据流执行节点出度查询可以判断指定路口的车辆驶出流量，执行边缘查询可以得到指定街道在某一个时间段的车流量，执行路经查询可以判断两个地点当前是否有路径可以到达，执行子图查询可以查询图数据流中多次出现的模式，提取出车辆在不同路口中穿行的规律，从而完成道路规划。

技术领域

[0001]本发明属于图数据处理的技术领域，更具体地，涉及一种基于滑动窗口的标签感知图形流草图构建方法及应用，该方法对图数据流领域中的异质流提出了快速准确的存储草图，提供了高效的存储方法和下游分析基础。

背景技术

[0002]由于科学技术的高速发展，在当前的大数据时代，数据在现实世界的网络中以不可预计的速度生成。截至2020年5月，推特平台上每年大约有2000亿条推文被分享，这意味着平均每秒产生约6000条推文，每分钟产生约350000条推文。图数据流用于对以边的形式顺序更新的图进行建模，作为静态图的扩展，它可以模拟真实场景中网络的连续演化。与静态图的挖掘类似，大规模图数据流的分析具有重要的现实意义。例如，对于社交网络而言，探索节点之间的联系有助于预测用户的潜在朋友或检测假新闻的来源。对于交通网络而言，拥堵路段预测和路线规划等下游应用也受益于此类分析。

[0003]由于图数据流数量庞大且变化率过大，准确地计算巨大图流上的边或节点的频率通常是无法实现的。目前常见的做法是构建基于草图的摘要，这可以显著减少图数据流占用的存储空间并获得极快的响应速度，同时这种方法在查询上的准确率损失是有限的。

[0004]目前绝大多数草图相关的研究都是基于同质数据流，也就是不包含任何标签信息的数据流。该方向的研究已经较为成熟，能够在仅损失极小的准确率的情况下完成草图的构建。但现实场景中产生的数据流大多是带有标签信息的。例如，在社交网络中，用户可以被视为节点，边代表用户之间的交互数据。用户可以根据他们的兴趣被分配到不同的社区，因此节点上具有不同的个人标签。用户之间的交流还可以根据交流的强度分为频繁、中等和不频繁。异构图数据流中节点和边承载着丰富的信息，忽视这些信息会导致严重的知识损失。

[0005]此外，目前的图数据流研究很少涉及对时间戳的处理，这意味着它们没有考虑插入速率对查询的影响，也没有在维护草图时区分不同时间点到达的项目。一方面，图数据流的更新频率代表了网络的活动状态，所以草图应该能具备携带时间戳的能力。另一方面，不同时间点到达的项目在实际应用中具有不同的重要性。越接近当前时间，项目就越有价值。滑动窗口通常用于解决以上问题，因此在草图中支持这一点。

[0006]为了解决上述问题，旨在为异质图数据流设计一个高效的草图，从而增强草图的表达能力，丰富可支持的查询类型。

发明内容

[0007]本发明的目的是解决当前图数据流草图研究领域中的信息缺失问题，将顶点标签、边缘标签和时间戳高效嵌入草图，丰富其表达能力，从而支持下游更多种类的查询和分析。本方法通过提出矩阵分块思想，在不增加存储代价的情况下高效嵌入项目的顶点标签，通过利用质数乘积的因式分解的唯一性提出双计数器机制，在仅使用一个质数的情况下完成多权重、多边缘标签的存储。同时，通过引入多个子窗口构成的滑动窗口模型，草图具备时间感知能力，能有效支持后续的结构化查询及时间敏感查询。

[0008]为实现上述目的，本发明提供如下技术方案：

[0009]基于滑动窗口的标签感知图形流草图构建方法，包括以下步骤：

[0010]S1、获取带有标签和时间戳的异质图数据流；

[0011]S2、根据图数据流中到达项目的时间戳对窗口进行滑动；

[0012]S3、确定图数据流中的任一项目在矩阵中的存储位置；

[0013]S4、对矩阵中存在冲突的项目使用额外池进行存储；

[0014]S5、融合存储矩阵和额外池两个部分，完成草图的最终构建。

[0015]本技术方案进一步的优化，所述步骤S1中图数据流数据集的预整理，按照时间戳顺序，依次处理图数据流中的项目。

[0016]本技术方案进一步的优化，所述步骤S2中设定滑动窗口的大小是W时间单位，通过将时间窗口划分为k个子窗口，每个子窗口包含W/k时间单位，在仅保留一个最近子窗口的起始时间tn的基础上可以完成草图的有效滑动，通过比对当前时间t与tn，t≥tn+W/k，则开启一个新的子窗口并剔除最远子窗口，实现子窗口的更新并完成整体窗口的滑动。

[0017]本技术方案进一步的优化，所述步骤S3包括，

[0018]3.1、利用基础的哈希技术和矩阵分块思想，根据项目的顶点标签定位其所在的矩阵块；

[0019]3.2、使用线性同余方法生成地址的候选列表，若没有冲突，则完成项目的定位过程；

[0020]3.3、使用双计数器机制，存储项目的边缘标签及对应权重。

[0021]本技术方案进一步的优化，所述步骤S3中针对处理的异质图数据流，假定当前到达图数据流的项目表示为e＝(A，B，lA，lB，le，w，t)，其中A和B为项目的两个顶点标识符，lA和lB是顶点对应的顶点标签，le是项目的边缘标签，w是项目的权重，t是项目的时间戳，标识项目到达图数据流的时间；首先利用项目的两个顶点标签lA和lB信息确定其所属的初始矩阵块，然后提取项目本身的标识符A和B作为信息在选定的矩阵块中游走，最终确定其在矩阵中的存储位置，并使用双计数器机制高效记录其到达的边缘标签及对应权重。

[0022]本技术方案进一步的优化，所述步骤S3包括，

[0023]3.1、根据顶点标签确定项目所属的矩阵块；

[0024]为了高效存储项目的顶点标签，使用矩阵分块思想，将具有相同顶点标签的项目聚集存储在同一个大块中，在不增加存储耗费的基础上完成顶点标签的嵌入，基于预先设置好的草图参数，包括矩阵宽度d、矩阵块宽度b，根据项目的两个顶点标签lA和lB得到对应的哈希值为H(lA)和H(lB)，进而将其转化为二维矩阵中每一维的定位标志H(lA)％m、H(lB)％m，其中m是一维中分块的数量，表示为d/b；由此，可以确定项目所属的矩阵块，该矩阵块的起始位置为(b*H(lA)％m，b*H(lB)％m)，该矩阵块的大小范围为：

[0025]A∈(b*H(lA)％m，b*H(lA)％m+b)

[0026]B∈(b*H(lB)％m，b*H(lB)％m+b)

[0027]3.2、根据标识符信息确定项目所属的矩阵格；

[0028]对项目的标识符A和B处理，得到哈希值以及对应的初始地址和指纹，分别为H(A)、H(B)；f(A)＝H(A)％F、f(B)＝H(B)％F，其中F是设定的指纹长度，

[0029]根据已有的线性同余方法，使用标识符A和B的指纹f(A)、f(B)作为种子，使用公式

[0030]

[0031]分别生成项目对应的地址候选序列{s1(A)，s2(A)，...，sr，(A)}、{s1(B)，s2(B)，...，sr(B)}，其中0≤si(A)≤b，0≤si(B)≤b，r是候选列表的长度，乘数T、增量I、模数M都是线性同余方程中的设定常量，依次检查候选列表并在项目选定的矩阵块中进行游走；若没有冲突，则完成项目在矩阵中的定位；

[0032]3.3、使用双计数器机制，存储项目的边缘标签及对应权重；

[0033]设计双计数器机制解决图数据流中同一项目多次以不同权重、不同边缘标签到达的统一性问题，定义数量计数器列表C＝{C1，C2，...，Ck}存储项目在不同时间窗口内的所有边缘的总体权重，此外，预定义一个质数列表PList＝{2，3，5，...}，使用哈希函数将每一个边缘标签映射到独有的质数上，利用质数乘积的因式分解的唯一性定义标签计数器列表P＝{P1，P2，...，Pk}，通过将多个时间点到达的具有不同权重、不同边缘标签的项目转化成质数，并乘入计数器列表P，从而在能够分解的情况下高效完成边缘标签的存储。

[0034]本技术方案进一步的优化，所述步骤S4包括，

[0035]4.1、根据顶点的标识符确定所属链表；

[0036]4.2、使用双计数器机制，存储项目的边缘标签及对应权重。

[0037]本技术方案更进一步的优化，所述步骤4.1中根据计算出的项目的顶点标识符的哈希结果H(A)、H(B)，通过对比H(A)找到以A为起始节点的单一链表，遍历该单一链表，若某一结点的存储内容为H(B)，则完成定位；否则，需要在该链表的尾部新增存储内容为H(B)的结点。

[0038]本技术方案进一步的优化，还包括步骤S6，通过查询，完成对图数据流的分析。

[0039]本技术方案进一步的优化，将该方法应用于交通网络，对图数据流执行节点出度查询可以判断指定路口的车辆驶出流量，执行边缘查询可以得到指定街道在某一个时间段的车流量，执行路经查询可以判断两个地点当前是否有路径可以到达，执行子图查询可以查询图数据流中多次出现的模式，提取出车辆在不同路口中穿行的规律，从而完成道路规划。

[0040]区别于现有技术，上述技术方案具有如下优点和有益效果：

[0041]本发明创新性地提出了可以应用在异质图数据流上的高准确率、高压缩度的图数据流摘要结构LSketch(Label-Enabled Graph Stream Sketch)。通过采用滑动窗口机制，LSketch能够保留项目的时间戳信息，从而反馈图数据流的插入速率、支持下游时间敏感的查询。此外，LSketch通过矩阵分块思想和双计数器机制，在不占用大量存储空间的前提下对顶点标签和边缘标签高效编码，能够支持下游无标签限制、有标签限制的各类查询。LSketch的构建更符合实际应用的需要，保留了异质图数据流中的各类有效信息，避免了知识损失。通过在草图上执行各类查询，可以完成对指定顶点、指定边缘以及固定模式的分析，从而完成对图数据流的分析，进一步可以进行下游的预测优化等。

附图说明

[0042]图1为基于滑动窗口的标签感知图形流草图构建方法的流程图；

[0043]图2为社交网络中异质图流的示意图；

[0044]图3为引入滑动窗口后矩阵格或链表结点的数据结构示意图；

[0045]图4为矩阵分块的示意图；

[0046]图5为矩阵块中地址列表检查与定位的示意图；

[0047]图6为额外池的数据结构示意图；

[0048]图7为实验数据集的窗口和子窗口的大小设定图；

[0049]图8为节点出度查询错误率的结果示意图；

[0050]图9为边缘查询错误率的结果示意图；

[0051]图10为路径查询正确率的结果示意图；

[0052]图11为子图查询错误率的结果示意图；

[0053]图12为有边标签限制的节点出度查询错误率的结果示意图；

[0054]图13为有边标签限制的边缘查询错误率的结果示意图；

[0055]图14为节点出度查询的响应时间；

[0056]图15为边缘查询的响应时间。

具体实施方式

[0057]为详细说明技术方案的技术内容、构造特征、所实现目的及效果，以下结合具体实施例并配合附图详予说明。

[0058]本发明提出了一种基于滑动窗口的标签感知图形流草图构建方法，参阅1所示，为基于滑动窗口的标签感知图形流草图构建方法的流程图。该方法的详细步骤如下：

[0059]第1、根据图数据流中到达项目的时间戳对窗口进行滑动

[0060]在实际应用中，随着图数据流的不断演化，老旧边缘的存在会对当前时刻的数据分析产生不利影响。此外，时间戳也能够表示图数据流中项目的插入速率。滑动窗是一种常见的用来处理时间戳的技术。因此，本草图设计了一个滑动窗口方案来自动处理边缘删除，确保图数据流的时效性，以支持后续的时间敏感查询。本发明设定滑动窗口的大小是W时间单位，通过将时间窗口划分为k个子窗口，每个子窗口包含W/k时间单位，这样处理能够增加草图的时间粒度并扩展下游查询的种类。本草图只保留在时刻t-W之后到达的项目，从而维护了整个草图的时效性。此外，现实世界中的查询大多与时间段有关，而不是特定的时间点。因此，维护所有项目的时间戳信息是没有必要的，草图在仅保留一个最近子窗口的起始时间tn的基础上可以完成整体的有效滑动，避免了冗余存储多个时间戳带来的存储浪费问题。通过比对当前时间t与tn，当t≥tn+W/k时，则开启一个最新的子窗口并剔除最远子窗口，从而实现子窗口的更新并完成整体窗口的滑动。通过以上机制，草图能够自动筛选出过于老旧的边缘并实现边缘删除，多个子窗口的设置能够增加草图的时间辨别能力。

[0061]第2、确定图数据流中的任一项目在矩阵中的存储位置

[0062]给定需要处理的异质图数据流，假定当前到达图数据流的项目表示为e＝(A，B，lA，lB，le，w，t)，其中A和B为项目的两个顶点标识符，lA和lB是顶点对应的顶点标签，le是项目的边缘标签，w是项目的权重，t是项目的时间戳，标识项目到达图数据流的时间。首先利用项目的两个顶点标签lA和lB信息确定其所属的初始矩阵块，然后提取项目本身的标识符A和B作为信息在选定的矩阵块中游走，最终确定其在矩阵中的存储位置，并使用双计数器机制高效记录其到达的边缘标签及对应权重。

[0063]第2.1、根据顶点标签确定项目所属的矩阵块

[0064]草图的设计注重效率和存储空间成本，为了高效存储项目的顶点标签，采用矩阵分块思想，将具有相同顶点标签的项目聚集存储，在不增加存储耗费的基础上完成顶点标签的编码。首先预置草图中矩阵的参数包括矩阵宽度d以及矩阵块宽度b，这意味着矩阵中的每一维被划分为长为b的段，每一段中存储具有相同顶点标签的顶点。根据项目的两个顶点标签lA和lB得到对应的哈希值为H(lA)和H(lB)，进而将其转化为二维矩阵中每一维的定位标志H(lA)％m、H(lB)％m，其中m是一维中分块的数量，表示为d/b。由此，可以确定该项目所属的矩阵块，该矩阵块的起始位置为(b*H(lA)％m，b*H(lB)％m)，该矩阵块在每一维的大小范围为：

[0065]A∈(b*H(lA)％m，b*H(lA)％m+b)、B∈(b*H(lB)％m，b*H(lB)％m+b)

[0066]第2.2、根据标识符信息确定项目所属的矩阵格

[0067]由于许多自然网络数据集中的顶点度分布遵循幂律分布，对于巨大的稀疏图而言，使用邻接矩阵通常是非常浪费空间的。因此，使用现有的指纹技术处理项目中的顶点，使得不同的顶点能够存储在矩阵中的同一行，以此增加矩阵的存储容量。首先，对项目的标识符A和B处理，得到哈希值以及对应的初始地址和指纹，分别为H(A)、H(B)；f(A)＝H(A)％F、f(B)＝H(B)％F，其中F是设定的指纹长度。

[0068]根据已有的线性同余方法，使用标识符A和B的指纹f(A)、f(B)作为种子，使用公式

[0069]

[0070]分别生成项目对应的地址候选序列{s1(A)，s2(A)，...，sr(A)}、{s1(B)，s2(B)，...，sr(B)}，其中0≤si(A)≤b，0≤si(B)≤b，r是候选列表的长度，乘数T、增量I、模数M都是线性同余方程中的设定常量。依次检查候选列表并在项目选定的矩阵块中进行游走。为了能够进一步增强矩阵的存储能力，将每一个矩阵格划分为两段，每一段具有单独的存储能力，该方法命名为双胞胎策略。在游走时，对每一个矩阵格，依次检查低位双胞胎段和高位双胞胎段。若存在某一个双胞胎段的指纹没有冲突，则完成项目在矩阵中的定位，否则，该项目无法在矩阵中存储，需要放置在额外池中。

[0071]第2.3、使用双计数器机制，存储项目的边缘标签及对应权重

[0072]在图数据流中，边会在同一对节点之间出现多次，即在不同时间携带不同的权重或标签。在最后构建的草图中，一条边的总权重是共享同一对端点的所有项目权重的总和。为了有效地保留标签信息，草图必须能够区分边缘标签并存储各自的权重。设计双计数器机制解决图数据流中同一项目多次以不同权重、不同边缘标签到达的统一性问题。定义数量计数器列表C＝{C1，C2，...，Ck}存储项目在不同时间窗口内的所有边缘的总体权重。此外，预定义一个质数列表PList＝{2，3，5，...}，使用哈希函数将每一个边缘标签映射到独有的质数上。利用质数乘积的因式分解的唯一性，定义标签计数器列表P＝{Ｐ1，P2，...，Pk}，通过将多个时间点到达的具有不同权重、不同边缘标签的项目转化成质数，并乘入对应的计数器列表P，从而在能够分解的情况下高效完成边缘标签的存储。

[0073]第3、使用额外池存储矩阵中存在冲突的项目

[0074]由于矩阵中存在指纹的检测，有冲突的项目不能叠加存储。针对有冲突的项目e＝(A，B，lA，lB，le，w，t)，定义额外池的数据结构为多链表结构，使用一个列表存储顶点的哈希值和链表头的一一映射关系。一个链表可以表示某一个顶点的出度情况，该顶点的所有出度顶点依次连接在该链表头的尾部。由于链表不能进行分块，使用项目的标识符A和B的哈希值H(A)、H(B)作为结点的存储内容进行冲突的判断。

[0075]第3.1、根据顶点的标识符确定所属链表

[0076]根据第1步的计算结果，即项目的顶点标识符的哈希结果H(A)、H(B)，在映射列表中比对H(A)，直到找到对应的链表头。遍历该单一链表，若某一结点的存储内容为H(B)，则完成当前需要存储的项目的定位；否则，需要在该链表的尾部新增存储内容为H(B)的结点，完成定位。

[0077]若没有在映射列表中找到H(A)，则说明当前不存在此链表。新建一个以H(A)为存储内容的链表头并在映射列表中更新索引。在该链表头的尾部新增存储内容为H(B)的结点，完成定位。

[0078]第3.2、使用双计数器机制，存储项目的边缘标签及对应权重

[0079]和第2.3的内容相同，在完成项目在额外池中的定位后，需要使用双计数器机制更新额外池中该项目的边缘标签及对应的权重。若在额外池中，该项目已经存在(即不需要新建链表或者结点)，则使用哈希函数将项目的边缘标签映射到某一个质数Pt上，在最新的子窗口上，更新Ck＝Ck′+w，重复更新Pk＝Pk′×Pt的操作w次。若该项目不存在，则需要新建结点，将其滑动窗口的数值全部置于初始状态，然后更新Ck＝w，重复更新Pk＝Pk′×Pt的操作w次。

[0080]第4、融合存储矩阵和额外池两个部分，完成草图的最终构建

[0081]在完成图数据流所有项目的插入后，草图的构建过程结束，此时存储矩阵和额外池将作为最终结果进行输出。

[0082]第5、通过各类下游查询，完成对图数据流的分析

[0083]在得到图数据流的概要草图后，可以通过执行各类查询完成对图数据流的分析，从而达到预测优化等目的。以交通网络为例，监管部门可以通过不断查询某一个路口的节点出度及入度来获取其流量，从而判断该路口在一周内的哪一天流量最高，然后动态调派人手。此外，为了统计整体的流量信息需要找出最拥堵的路段或者车辆最常的行驶路径，通过执行子图查询，找出该图数据流中多次出现的模式，从而提取出车辆在不同路口中穿行的规律，在道路规划时可参考频繁模式提醒用户进行避让。

[0084]本发明优选一实施例，该实施方案包括：图数据流数据集的预整理；按照时间戳顺序，依次处理图数据流中的项目，处理步骤包括：1)根据项目的时间戳，完成时间窗口的滑动；2)根据矩阵分块思想，确定项目所属的矩阵块；根据基础的指纹技术和线性同余方法，确定项目所属的矩阵格，完成定位；如果项目在该矩阵格中不存在冲突，根据双计数器机制，更新项目的边缘标签及对应权重；3)如果项目在矩阵中存在冲突，则在额外池中完成定位；使用双计数器机制，更新项目的边缘标签及对应权重。最后，基于构建的概要草图，执行各类查询以完成网络的分析优化。

[0085]第1、根据图数据流中到达项目的时间戳对窗口进行滑动

[0086]假定当前到达图数据流的项目表示为e＝(A，B，lA，lB，le，w，t)，其中A和B为项目的两个顶点标识符，lA和lB是顶点对应的顶点标签，le是项目的边缘标签，w是项目的权重，t是项目的时间戳，标识项目到达图数据流的时间。

[0087]如图2所示，为社交网络中异质图流的示意图，社交网络中的用户被建模为节点，用户之间的互动被建模为边。其中，用户个人的特征可以作为他的顶点标签，如音乐家、画家。边缘标签可以表示为用户在发送消息时选择的紧急级别，如普通、紧急。此外，消息的长度表示边的权重，消息发送的时间是时间戳。根据图2，图数据流中的项目(边)e＝(A，B，lA，lB，le，w，t)的某一个具体示例为：

[0088]e＝(Tom，Lily，Musician，Painter，Normal，5，2021-9-9 14:00:20)。

[0089]在实际应用中，随着图数据流的不断演化，老旧边缘的存在会对当前时刻的数据分析产生不利影响。时间戳标志着项目的新旧程度，滑动窗口是修剪老旧项目的常用技术。本发明设定滑动窗口的大小是W时间单位，通过将时间窗口划分为k个子窗口，每个子窗口包含W/k时间单位，使得草图的时间粒度增加并扩展下游查询的种类。在仅保留一个最近子窗口的起始时间tn的基础上可以完成草图的有效滑动，避免了冗余保留多个时间戳带来的存储浪费问题。通过比对当前时间t与tn，t≥tn+W/k，则开启一个新的子窗口并剔除最远子窗口，实现子窗口的更新并完成整体窗口的滑动。

[0090]当图数据流中不断到达新的项目时，首先进行滑动窗口的处理。参阅图3所示，为引入滑动窗口后矩阵格或链表结点的数据结构示意图。根据实际需求，对当前社交图数据流设置滑动窗口的大小W＝100，k＝10，因此一共有10个大小为10s的子窗口。假定目前tn＝90，这意味着当前窗口表示的时间范围是[0，100)。t＝100到达一个新的项目，由于t≥tn+W/k，因此需要对整体的窗口滑动。此时，开启一个新的子窗口并舍弃最旧的子窗口，完成老旧边缘的删除。更新tn＝90+10＝100，此时当前窗口表示的时间范围是[10，110)。

[0091]第2、确定图数据流中的任一项目在矩阵中的存储位置

[0092]首先利用项目的两个顶点标签lA和lB信息确定其所属的初始矩阵块，然后提取项目本身的标识符A和B作为信息在选定的矩阵块中游走，最终确定其在矩阵中的存储位置，并使用双计数器机制高效记录其到达的边缘标签及对应权重。

[0093]根据图数据流的预估大小，设定草图中矩阵的宽度d＝50，矩阵块的宽度b＝10，因此矩阵中每一维被分为5段，每一段是某一类顶点标签的存储位置。在完成时间窗口的滑动后，开始对到达的项目进行定位。

[0094]第2.1、根据顶点标签确定项目所属的矩阵块

[0095]假定当前到达的项目为e＝(Tom，Lily，Musician，Painter，Normal，5，2021-9-914:00:20)，首先使用两个顶点标签获取初始信息。使用BOB哈希方法，得到顶点Tom的矩阵块定位为H(Musician)％(d/b)＝20003120％5＝0。同理，得到Lily的矩阵块定位为H(Painter)％(d/b)＝43755533％5＝3。因此，该项目应该存储在第[0，3]个矩阵块中，第一维的有效存储范围为[10×0，10×0+10)＝[0，10)，第二维的有效存储范围为[10×3，10×3+10)＝[30，40)。图4阐释了矩阵分块的示意图。

[0096]第2.2、根据标识符信息确定项目所属的矩阵格

[0097]接下来，根据到达项目的标识符信息确定其所属的矩阵格。根据图数据流的度偏移等特征，预定义指纹长度为10bit，即F＝210＝1024。按照公式f(v)＝H(v)％F分别代入Tom和Lily的哈希值，计算结果如下：

[0098]

[0099]

[0100]f(Tom)＝H(Tom)％F＝374293462％1024＝982，

[0101]f(Lily)＝H(Lily)％F＝39041807％1024＝783。

[0102]接下来，预设定线性同余方程中的乘数T、增量I、模数M。注意，以上三个参数需满足：1、I，M互质；2、M的所有质因数都能整除T-1。假定取乘数T＝5、增量I＝3、模数M＝8，则线性同余方法生成随机数的方式如下：

[0103]

[0104]，分别代入Tom和Lily的指纹作为种子，即可得到各自的地址候选列表。假定r＝4，则结果为：

[0105]s(Tom)＝{1，0，3，2}

[0106]s(Lily)＝{6，1，0，3}

[0107]因此，在插入该项目时，在第[0，3]个矩阵块中游走，依次检查双胞胎段然后判断是否存在冲突。例如，首先检查第[0，3]个矩阵块的第(1，1)个位置[1，6]，即全局矩阵中的[1，36]。若该位置冲突，则检查第[0，3]个矩阵块的第(1，2)个位置[1，1]，即全局矩阵中的[1，31]，后续过程以此类推。若在地址的候选列表中存在不冲突的矩阵格，则该项目可以顺利存储在矩阵中，否则需要放入额外池。关于冲突判断，首先需要检查项目存储的索引对。在检查矩阵块的第(1，1)个位置[1，6]时，假定在双胞胎策略下该矩阵格中存储的索引对(ir，ic)分别为(2，4)、(1，5)，由于其与(1，1)均不匹配，存在冲突。接下来，检查矩阵块的第(1，2)个位置[1，1]，假定该矩阵格中低双胞胎段存储的索引对(ir，ic)为(1，1)，不存在冲突。因此进一步检查项目存储的指纹对，假定该矩阵格中低双胞胎段存储的指纹对(f(A)，f(B))为(982，783)，与项目的指纹对相同，则完成定位。图5阐释了项目如何在矩阵块中完成地址列表的检查与定位。

[0108]第2.3、使用双计数器机制，存储项目的边缘标签及对应权重

[0109]完成定位后，需要更新项目的边缘标签及权重。在第1步中，窗口已经完成了滑动，因此只需要在最新的子窗口中更新项目的影响即可。对于项目e＝(Tom，Lily，Musician，Painter，Norma1，5，2021-9-9 14:00:20)，按照图数据流中边缘标签的个数预定义质数列表为PList＝{2，3，5，7，9}，其长度c＝5。使用BOB哈希函数，将该项目的边缘标签映射到列表中的某一个质数上，例如lt＝H(Normal)％c＝10032％5＝2，则“Normal”被映射到质数PList[2]＝3。对计数器列表C，更新Ck＝Ck′+w，即C10＝4+5＝9。对计数器列表P，按照Pk＝Pk′×lt更新w次，即P10＝40×3×3×3×3×3＝9720。

[0110]第3、使用额外池存储矩阵中存在冲突的项目

[0111]额外池的数据结构为多链表结构，使用一个列表存储顶点的哈希值和链表头的一一映射关系，额外池的数据结构如图6所示。一个链表可以表示某一个顶点的出度情况，该顶点的所有出度顶点依次连接在该链表头的尾部。假定项目e＝(Tom，Lily，Musician，Painter，Normal，5，2021-9-9 14:00:20)在矩阵中的所有候选地址都存在冲突，现需要在额外池中定位该项目并存储。

[0112]第3.1、根据顶点的标识符确定所属链表

[0113]根据第1步的计算结果，首先使用Tom的哈希结果H(Tom)找到Tom对应的出度链表。在映射列表中比对H(Tom)，如果存在匹配的映射关系，则表明当前已经存在该链表。例如，当前的映射列表为[(23859123，0)，(330029455，1)，(98749473，2)，(374293462，3)]，根据匹配项(374293462，3)得知Tom对应的链表索引为3，即可取出所需的链表。遍历该单一链表，比对每一个链表结点的存储内容。若某一结点的存储内容为H(Lliy)，则完成当前需要存储的项目的定位；否则，需要在该链表的尾部新增存储内容为H(Lily)的结点，完成定位。

[0114]若没有在映射列表中找到H(Tom)，则说明当前不存在此链表。假定当前的映射列表为[(23859123，0)，(330029455，1)]，由于不存在H(Tom)的匹配项，需新建以Tom为头结点的链表，并在映射列表中更新索引[(23859123，0)，(330029455，1)，(374293462，2)]。对新建的链表，在尾部增加存储内容为H(Lily)的结点，完成定位。

[0115]第3.2、使用双计数器机制，存储项目的边缘标签及对应权重

[0116]和第2.3的内容相同，在完成项目在额外池中的定位后，需要使用双计数器机制更新额外池中该项目的边缘标签及对应的权重，不赘述。

[0117]第4、融合存储矩阵和额外池两个部分，完成草图的最终构建

[0118]针对每一个到达图数据流的项目，重复第1、2、3步，最终完成草图的构建。此时存储矩阵和额外池将作为最终结果输出。

[0119]第5、提升下游图查询任务准确度

[0120]为了完成对图数据流的分析，需要基于用户的需求对其执行各类查询以完成模式挖掘、流量预测等任务，进一步实现优化。以交通网络为例，对图数据流执行节点出度查询可以判断指定路口的车辆驶出流量，执行边缘查询可以得到指定街道在某一个时间段的车流量，执行路经查询可以判断两个地点当前是否有路径可以到达，执行子图查询可以查询图数据流中多次出现的模式，提取出车辆在不同路口中穿行的规律，从而完成道路规划。在得到图数据流的概要草图后，可以通过执行各类查询完成对图数据流的分析，从而达到预测优化等目的。具体而言，当用户想要确定某一个路口在一周内的流量模式，则需要设置窗口大小为1周，子窗口大小为1天。在构建完草图后，对指定的路口执行节点度查询，从而判断该路口在一周内的哪一天流量最高。根据结果，用户可以选择流量较低的日期出行从而避免拥堵。此外，为了统计整体的流量信息需要找出最拥堵的路段或者车辆最常的行驶路径，通过执行子图查询，找出该图数据流中多次出现的模式，从而提取出车辆在不同路口中穿行的规律，在道路规划时可参考频繁模式提醒用户进行避让。

[0121]本方法可以作为黑盒完成各类结构化查询，因此能保证用户使用草图完成下游分析及应用，并且查询的准确率和响应时间都远优于现有方法。

[0122]本方法在下游图查询任务(包括节点的出度查询、边缘查询、路经查询和子图查询)的准确度指标是错误率和准确率，错误率的计算方法为：其中ress是草图的查询结果，res是真实结果，|E|是图数据流的边数；准确率在路经查询中使用，计算方法为：Accuracy＝the number of false positives/the number of queries。

[0123]实验选取了四个不同领域的真实数据集，分别为网站中提供的数据集phone(http://crawdad.org/mit/reality/20050701/)、数据集Road(https://data.gov.hk/sc-data/dataset/hk-td-sm_1-traffic-speedmap)、数据集enron(http://www.ahschulz.de/enron-email-data/)以及斯坦福数据分析平台提供的数据集com-FS(http://snap.stanford.edu/data)。针对同质数据集com-FS，使用随机方法为其生成标签信息和时间戳。根据图数据流的实际应用及其总体时间跨度，每个数据集的窗口大小和子窗口大小如图7所示。

[0124]实验选取的对比方法分别为处理同质图数据流的草图方法GSS和处理异质图数据流的草图方法LGS。GSS的基础设置和LSketch一致；针对LGS，选取副本个数为4。

[0125]图8展示了三种方法在四个数据集上的节点出度查询结果。在所有数据集上，本方法的查询准确率相较于LGS实现了极大的提升。在Phone数据集上，LSketch的准确性略低于GSS。在其他数据集上，LSketch实现了与GSS相同的精度。值得注意的是，LSketch比GSS多编码两个顶点标签和一个边缘标签，同时还保留了图数据流的时间戳信息，因此以上实验结果证明了本方法在顶点标签保存方面的有效性和准确性。

[0126]图9展示了三种方法在四个数据集上的边缘查询结果。这三种方法在边缘查询上都表现较好。值得注意的是，LSketch和GSS对所有数据集的准确率都接近100％，而LGS没有能力区分存储在同一位置的不同项目，因此错误率略高。

[0127]图10展示了三种方法在四个数据集上的路径查询结果。草图只存在假阳性，因此只有当真实结果为假而草图返回真时才会发生错误。基于以上信息，使用准确性衡量草图在边缘查询上的性能。Road数据集是一个连通图，所以其精度始终为1。对于其他数据集，LSketch的精度与GSS相当，远远优于LGS。

[0128]图11展示了近似子图查询的结果。由于GSS不保留边缘信息，无法支持子图查询，因此仅展示LSketch和LGS的实验结果。近似子图匹配查询是边缘查询的重复执行，所以其结果与边缘查询的结果非常相似，LSketch的错误率远低于LGS。

[0129]此外，为了展示LSketch维护标签信息的优势，图12和图13分别展示了带有边缘标签限制的节点出度查询和边缘查询的结果。由于GSS只能处理同质图数据流，不保留标签信息，因此GSS不能支持此类查询。针对边缘标签，质数列表的长度c越大，边缘标签碰撞的概率越小，从而错误率也越低。从图12和图13可以看出，与LGS相比，LSketch在错误率上的表现很好。在相同的参数设置下，LSketch的性能要比LGS好很多。此外，LSketch不需要使用多个草图来提高查询的准确性，这体现了LSketch在编码信息、节省空间和查询回答的高效率。

[0130]第6、提升下游图查询任务响应时间

[0131]具体实验采用和第5点相同的实验设置，包括使用的四个真实数据集、GSS对比方法以及相应的参数设置。以节点出度查询实验为例，使用对四个数据集分别执行查询。结果如图14所示，其中Raw data表示直接在图数据流上进行查询。由图中的数据可以看出，在较小的数据集上，LSketch和GSS都能在10us内完成查询；在极大的数据集上，LSketch和GSS的时间耗费略多，但也保持在us级别。相比而言，直接在图数据流上进行查询的时间耗费过大，通常需要花费几十毫秒或者几十秒。图15展示了在边缘查询上的时间结果。和节点出度查询相似，LSketch和GSS这类草图方法在查询的响应时间方面具有极大的优势。由图中的数据可以看出，草图比原始数据查询快几个数量级。在查询过程中，LSketch需要进一步处理两个顶点标签，因此时间消耗略高于GSS。即便这样，LSketch和GSS的差距几乎可以忽略不计，因为所有的查询都可以在us级别的时间内完成。

[0132]综上所述，本方法能够高效地存储异质标签信息，从而更好地支持后续的各类查询。与现有方法比较，LSketch能够在草图响应时间以及查询准确度两个方面维持极大的优势，这表明了本方法的竞争力。

[0133]需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者终端设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者终端设备所固有的要素。在没有更多限制的情况下，由语句“包括……”或“包含……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者终端设备中还存在另外的要素。此外，在本文中，“大于”、“小于”、“超过”等理解为不包括本数；“以上”、“以下”、“以内”等理解为包括本数。

[0134]尽管已经对上述各实施例进行了描述，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例做出另外的变更和修改，所以以上所述仅为本发明的实施例，并非因此限制本发明的专利保护范围，凡是利用本发明说明书及附图内容所作的等效结构或等效流程变换，或直接或间接运用在其他相关的技术领域，均同理包括在本发明的专利保护范围之内。