聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

ICDE'22:支持时间范围查询的图流概要结构Horae

2022-09-15 12:09 浏览: 3281966 次 我要评论(0 条) 字号:

如何对大规模的图流数据进行高效的存储,并提供与图拓扑相关和时间相关的查询是一个核心问题。图流作为一种实时动态的关联数据模型,结合了图的关联表示性和流的连续更新性,广泛应用于大数据应用中,其形式为一条随着时间不断演化的边流序列。因数据不断到来而产生的超大规模图流很难被完整地存储在内存中,基于近似存储并提供多样化查询的图流概要技术成为了管理图流数据的可行方向。

现有的图流概要技术都通过哈希函数将图流压缩为更小的草图Gs,再利用一个空间高效的矩阵存储Gs。对于每个元素,它们将顶点信息映射到矩阵的行和列上面,将边的权重信息存储在对应的单元。包含相同顶点的边会存在相同行或列上,维护了元素之间的关联性,保留了图的拓扑信息。因此能支持各种图拓扑相关的查询,比如边聚合权重查询、顶点聚合权重查询、边存在性查询和路径可达性查询等。然而,现有的图流概要结构均没有利用图流时间维度的信息,无法支持时间范围查询。设计支持时间范围查询的图流概要结构有三点挑战。第一,完整地存储时间信息的内存开销对于简洁的图流概要结构是不可接受的。第二,离散地存储时间信息导致过高的查询时延。第三,结构需要适应图流在时间维度的动态增长性。

针对图流的时间范围查询,研究小组提出时间前缀嵌入的多层图流概要结构——Horae。Horae设计了一种时间嵌入的存储方式,将时间信息和顶点信息结合在一起并隐式地存储在结构中,无额外的内存开销。在时间的二进制表示下,Horae进一步利用多层结构和基于时间前缀的数据存储方式,在不同层中根据不同长度的时间前缀组织图流数据。在每一层中,包含相同前缀的时间信息会合并成一个子范围信息,图流数据相应地按照子范围进行聚合。在每层结构中可以直接获取一个子范围的数据。基于子范围查询,进一步提出了一种高效的二元范围分解算法,将任意时间范围的查询分解成多个在不同层的子范围查询,提供对数级别的查询处理。并且Horae结构会随着图流演化不断扩展层数,在扩展过程中通过数据复制保证所有时间的数据都存储在每层中。通过充分的实验全面评估了Horae在大规模真实图流数据集上的性能。结果表明,与目前国际上最好的图流概要结构在相同内存配置下相比,Horae将多种时间范围查询的时延显著降低了两至三个数量级,同时将查询误差降低一至两个数量级。

Horae结构已经开源,相应论文成果“Horae: A Graph Stream Summarization Structure for Efficient Temporal Range Query”发表在ICDE 2022上。

  • 论文链接:

    https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9835395

  • 开源链接:

    https://github.com/CGCL-codes/Horae


背景与问题

图流从形式上是一个包含时间信息的边流序列,序列中每个元素ei 被表示为(si, di, wi, ti),表示一条由源顶点si 和目的顶点di构成的有向边,该边带有权重wi以及在时间ti产生。随着边的不断到来,形成一个随着时间不断演化的图G = (V, E)。图流有五个特点。第一,图流结合了图的通用表示性,图能表示实体之间的关系,同样图流中的元素之间具有关联性。第二,图流具有高速流动性和动态性,图流中的元素都是实时产生的,且图G随着每个元素的到来而更新。第三,图流通常包含了大量重复边,相同顶点的边可能会带着不同的权重在不同的时刻多次出现。第四,和数据流一样,图流中的每个元素只能被处理一次,即一过性。第五,时间相关性,每个元素都有个产生时间,图流随着时间在不断演化。图流作为一种动态关联的数据模型,广泛用于大数据应用中,比如数据中心的网络安全监测、新冠疫情期间的密切接触者追踪和智慧城市中的车辆监控等。图1展示了上述三个应用产生的图流数据日志,图1(a)中每个日志表示客户端和服务器端之间的一次通信,图1(b)中每个日志表示某人在某个地方某个时间通过扫码进出,图1(c)中每个日志表示某个车辆被某个摄像头捕捉。

图1 三个应用产生的图流数据日志

为了管理大规模的图流数据,图流概要技术使用基于哈希的压缩矩阵近似地存储图流,并提供和图拓扑相关的多样化查询。然而,现有的图流概要结构只能支持图拓扑相关的查询。它们都没有对图流时间维度的信息进行利用,所以无法支持时间相关的查询。可以将图流抽象成按照一个时间粒度划分的模型,该时间粒度用符号gl 表示。在此模型下,连续的时间被划分成了离散的时间片序列{T0, T1, …, Tu, …},Ti 表示第i + 1 个长度为gl 的时间片,Tu 表示图流的当前时间片且Tu 是不断增长的,两个时间片定义一个时间范围。基于现有的图流概要结构,使它们支持时间相关的查询的一个基本方法就是将边和所属时间片信息结合在一起执行插入操作和查询操作。但是执行一个时间范围为[Tb, Te]的查询,需要将[Tb, Te]分解为一系列的时间片{Tb, Tb+1, …, Te},并依次对每个时间片的数据进行查询。为了进一步验证该问题,研究小组用此方法将现有图流概要结构TCM和GSS分别扩展,并通过实验进行性能分析。图2的实验结果同样表明查询时延和查询范围长度成线性关系。当查询范围较大时,现有图流概要结构的查询时延难以接受。

图2 TCM和GSS的时间范围点查询时延


设计与实现

针对以上问题,研究小组设计了一个时间前缀嵌入的多层图流概要结构——Horae。Horae结构初始只有一层,并且会随着图流演化不断扩展层数。图3(a)展示了当前时间片等于T3时的Horae结构,层数为三;图3(b)展示了当前时间片等于T4时的Horae结构,层数为四。Horae在所有层中根据不同的时间前缀长度组织图流数据。在每一层中,包含相同前缀的时间信息会合并成一个子范围信息,图流数据也会相应地按照子范围进行聚合。每层中的子范围长度相同,该范围长度也称为每层的粒度。简而言之,每层包含一个压缩矩阵和一个邻接数组对相应粒度的图流进行概要存储。

当图流中的每个元素到来时,Horae需要将其插入到当前结构的所有层。在每层中,为了按照子范围聚合数据,Horae需要将边和时间片所属的前缀值结合进行插入。这是因为前缀的长度会随着层数的增加而增加,而前缀值保持不变。例如,在图3(a)和图3(b)中,子范围[T2, T3]的前缀分别为‘01’和‘001’,但是前缀值都为1。每当图流当前时间片增长到一个二次幂大小,Horae结构会向上扩展一层,并且通过数据复制保证每层数据的完整性。在图3中,Horae结构从三层扩展至四层时,T0T3的所有数据已经流过,第四层需要从第三层复制[T0,T3]的数据,即第四层的矩阵复制第三层矩阵中所有的数据,第四层的邻接数组复制第三层邻接数组的所有数据。并且由于[T0, T3]的前缀值和[T0, T7]的前缀值都为0,因此能保证数据复制的正确性。

图3 Horae结构

在Horae结构的每层中,可以通过与子范围前缀值结合的方式直接查询一个子范围的数据。基于子范围查询,研究小组进一步提出二元范围分解算法将任意的时间范围查询分解成多个在不同层的子范围查询。对于任意一个查询范围(假设长度为L),它的分布包含三种情况:一是完全对齐,即与某个子范围完全对齐;二是半对齐,即与某个子范围的一端对齐;三是不对齐。图4展示了上述三种情况以及对应的分解过程。在情况一中,该查询范围本身就是一个子范围,无需分解。情况二又分为左对齐和右对齐,分别表示该范围与某个子范围的左端和右端对齐。在该情况下,分解该范围等同于分解该范围长度。即将L转化为二进制形式,也就是通过位移操作将其写成多个二次幂相加的形式。如果是左对齐,则从对齐点依次往右从大到小地增加一个二次幂大小;如果是右对齐,则从对齐点往左依次减小一个二次幂大小。在情况二中,最多分解得到logL个子范围,这是因为长度L包含logL比特。在情况三中,可以先将该查询范围划分为两个小的范围,并且这两个范围分别为右对齐和左对齐。再按照情况二的半对齐方式对这两个范围进行分解。在该情况下,最多分解得到2logL个子范围。通过多层存储和二元范围分解算法,Horae结构能提供对数级别的查询处理。

图4 二元范围分解

通过多个真实图流数据集对Horae结构进行全面的性能分析,结果表明在内存配置一样的情况下,与目前国际上最好的图流概要结构TCM和GSS相比,Horae降低多种查询的时延两至三个数量级,并降低查询误差一至两个数量级。

图5 Horae性能对比


参考文献:
Ming Chen, Renxiang Zhou, Hanhua Chen, Jiang Xiao, Hai Jin, Bo Li. Horae: A Graph Stream Summarization Structure for Efficient Temporal Range Query. In: Proceedings of the 38th IEEE International Conference on Data Engineering (ICDE 2022), Virtual Event, Kuala Lumpur, Malaysia, May 9-12, 2022
系统开源:

https://github.com/CGCL-codes/Horae



网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复