面向周期边查询的高效图流概要技术  

Efficient graph stream summarization technology for periodic edge queries

作　　者：李卓 刘帅君 刘开华 LI Zhuo;LIU Shuaijun;LIU Kaihua(School of Microelectronics,Tianjin University,Tianjin 300072,China;Pengcheng Laboratory,Shenzhen 518000,China;Tianjin Microelectronics Technology Key Laboratory of Imaging and Perception,Tianjin 300072,China;Tianjin Digital Information Technology Research Center,Tianjin 300072,China;School of Information and Intelligent Engineering,Tianjin Ren’ai College,Tianjin 301636,China)

机构地区：[1]天津大学微电子学院,天津300072 [2]鹏城国家实验室,广东深圳518000 [3]天津市成像与感知微电子技术重点实验室,天津300072 [4]天津市数字信息技术研究中心,天津300072 [5]天津仁爱学院信息与智能工程学院,天津301636

出　　处：《浙江大学学报(工学版)》2025年第1期70-78,共9页Journal of Zhejiang University:Engineering Science

基　　金：国家重点研发计划资助项目(2022YFB2901100,2022ZD0115303);鹏城实验室算力网重大攻关项目(PCL2023A06).

摘　　要：当前图流概要技术不能在小内存下实现高效准确的图流测量,也无法完成周期边查询,为此提出面向周期边查询的图流概要技术——周期交互矩阵(PIM).PIM为混合结构,由存储重边的二维邻接矩阵和存储轻边的三维邻接矩阵组成,提高了内存效率.二维邻接矩阵保留重边标识、权重和时间戳,实时完成包括周期边查询在内的多种查询任务.设计基于权重和时间的替换策略,使用共享哈希技术以提高查询精度和插入查询效率.实验结果表明,PIM在小内存下实时高效地完成了多种图流查询任务,能够准确地召回所有频繁边、频繁点和周期边.对比当前图流概要技术,PIM将查询任务的平均相对误差降低了91.41%~99.54%.A graph stream summarization technology for periodic edge query named periodic interaction matrix(PIM)was proposed to address the problem that the current graph stream summarization technology cannot achieve efficient and accurate graph stream measurement under smaller memory and cannot complete periodic edge query.PIM was designed as a hybrid structure consisting of a two-dimensional adjacency matrix and a three-dimensional adjacency matrix.The heavy edges were stored by the two-dimensional adjacency matrix,the light edges were stored by the three-dimensional adjacency matrix,and the memory efficiency was enhanced.Heavy edge identifiers,weights,and timestamps were retained in the two-dimensional adjacency matrix to complete various query tasks in real-time,including periodic edge queries.A weight-based and time-based replacement strategy was designed,using a shared hashing technology to improve query accuracy and insertion query efficiency.Experimental results show that PIM can efficiently complete a variety of graph stream query tasks in real-time and with small memory,and can accurately recall all heavy hitter edges,heavy hitter nodes,and periodic edges.Compared to the current graph stream summarization technology,PIM reduces the average relative error of query tasks by 91.41%-99.54%.

关 键 词：图流 图流概要 周期边测量 实时查询 邻接矩阵 

分 类 号：TP393.0[自动化与计算机技术—计算机应用技术]