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

作     者：李卓 刘帅君 刘开华 LI Zhuo;LIU Shuaijun;LIU Kaihua

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

出 版 物：《浙江大学学报(工学版)》 (Journal of Zhejiang University:Engineering Science)

年 卷 期：2025年第59卷第1期

页      面：70-78页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

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

主　　题：图流 图流概要 周期边测量 实时查询 邻接矩阵 

摘      要：当前图流概要技术不能在小内存下实现高效准确的图流测量,也无法完成周期边查询,为此提出面向周期边查询的图流概要技术——周期交互矩阵(PIM).PIM为混合结构,由存储重边的二维邻接矩阵和存储轻边的三维邻接矩阵组成,提高了内存效率.二维邻接矩阵保留重边标识、权重和时间戳,实时完成包括周期边查询在内的多种查询任务.设计基于权重和时间的替换策略,使用共享哈希技术以提高查询精度和插入查询效率.实验结果表明,PIM在小内存下实时高效地完成了多种图流查询任务,能够准确地召回所有频繁边、频繁点和周期边.对比当前图流概要技术,PIM将查询任务的平均相对误差降低了91.41%~99.54%.