基于滑动窗口的标签感知图形流草图构建方法及应用

摘要

本发明属于图数据处理的技术领域，更具体地，涉及一种基于滑动窗口的标签感知图形流草图构建方法及应用。该方法首先，对于图数据流中的每个项目，使用现有的哈希方法和指纹技术获得项目的初始地址和指纹。其次，通过矩阵分块技术根据项目的顶点标签对其进行定位，并使用线性同余方法生成地址候选列表。稍后，设计双计数器机制高效存储项目的边缘标签及对应权重。最后，使用额外池存储矩阵中的冲突项目。本发明能够解决图数据流草图构建领域中的信息缺失问题，将顶点标签、边缘标签和时间戳高效嵌入草图，丰富了其表达能力。基于构建的草图，能够支持下游更多种类的查询和分析，例如交通网络中的路线规划以及社交网络中的虚假新闻检测。