近日，2020级硕士生蒋志国（指导老师：陈汉华教授）的论文“Auxo: A Scalable and Efficient Graph Stream Summarization Structure”被第49届超大型数据库国际会议（The 49th International Conference on Very Large Databases，VLDB 2023）录用。

图流（Graph Stream）模型能够表示实体与实体之间或实体内部直接实时联系的产生，因此被广泛地应用于诸多领域。图流具有的数据体量巨大、流速快、边界不可预知等特点，给数据管理带来严峻挑战，图流概要作为可行技术方向，近年来受到广泛关注。国际上现有概要结构通过将图流中的边哈希到大小固定的压缩矩阵中，并使用指纹二进制序列对边进行标记，在损失可控精度的前提下，实现了对图流数据时间和内存高效的存储。然而，现有的概要结构无法对规模动态增长的超大型图流数据提供系统可扩展支撑。

为了解决这一问题，提出了一种指纹前缀嵌入树（Prefix Embedded Tree， PET）模型。该模型在扩展时，通过将边的指纹标记嵌入到树型扩展结构中，在实现对指纹前缀信息无损压缩的同时，利用指纹前缀作为索引，将插入/查询时间复杂度降低到了对数级别。同时，为了提高扩展结构的内存利用效率，还提出了针对PET扩展结构的比例增量扩展策略（Proportionally Incremental Strategy），将指数级的扩展转换为比例增量式的扩展。基于以上技术，开发了可高效扩展的图流概要结构——Auxo（https://github.com/CGCL-codes/Auxo）。Auxo支持多种图查询算法，并获得了理想的时空复杂度和误差。采用大量真实系统超大规模图流数据，对Auxo的性能进行了性能测试。结果表明，Auxo在不同的图查询算法上均将现有工作的延迟降低了一到两个数量级，实现了可扩展的图流概要结构。

VLDB会议是数据领域的顶级国际学术会议，是中国计算机学会（CCF）推荐的A类会议,发表的论文备受各界关注。

（通讯员：蒋志国）