标签约束可达查询的高效处理方法

发布时间：2021-03-26 23:19

　　基于标签约束的可达性查询s→_Lt用于回答给定图中顶点s到顶点t是否存在路径标签属于L的有向路径.针对现有方法索引构建时间长、索引规模大、查询效率低的问题,首先基于k个点构建双向路径标签索引,并提出相应的优化措施减小索引规模,以此来加速可达查询的处理速度.由于其索引没有完全覆盖可达查询,虽然索引规模小,但仍然无法避免查询过程中的图遍历操作.为此,进一步提出覆盖所有可达信息的双向路径标签索引,基于该索引,查询处理时可以完全避免图上的遍历操作.最后,基于多个真实数据集进行测试,实验结果从索引大小、索引构建时间和查询响应时间方面验证了所提方法相对现有方法具有索引规模小、索引时间短且查询响应快的优势. 

【文章来源】：计算机研究与发展. 2020,57(09)北大核心EICSCD

【文章页数】：12 页

【部分图文】：

不同规模数据集上的索引大小对比

可达查询的查询时间对比

例1. 针对图1,假设顶点的处理顺序是v2→v4→v3→v5→v1→v0,根据以上思路建立的索引如表2所示.显然,这种索引虽然可回答所有查询,但存在很多冗余路径,索引规模过大.例如,inLabel(v4)中同时包含(v0,c),(v0,ac),(v0,bc).当给定查询v0→bv5,outLabel(v0)与inLabel(v5)的交集为{v0,v1,v2,v3,v5},将交集顶点对应的标签取并集.对于顶点v0:?∪ab=ab,?∪ac=ac,?∪abc=abc;对于顶点v1:c∪a=ac,c∪ab=abc;对于顶点v2:b∪a=ab,ac∪a=ac;对于顶点v3:ac∪b=abc;对于顶点v5:ab∪?=ab,ac∪?=ac,abc∪?=abc.这些并集标签均不是查询给定约束标签b的子集,因此v0bv5.显然,如果查询不可达,处理效率低.表2 初始路径标签索引Table 2 The Initial Path Label Index for Fig. 1 Node inLabel outLabel v0 {(v0,?)} {(v0,?),(v1,c),(v2,b),(v2,ac),(v3,ac),(v4,c),(v4,ac),(v4,bc),(v5,ab),(v5,ac),(v5,abc)} v1 {(v0,c),(v1,?)} {(v1,?),(v2,a),(v3,a),(v4,ac),(v5,a),(v5,ab)} v2 {(v0,b),(v0,ac),(v1,a),(v2,?)} {(v2,?),(v4,c),(v5,a)} v3 {(v0,ac),(v1,a),(v3,?)} {(v3,?),(v5,b)} v4 {(v0,c),(v0,ac),(v0,bc),(v1,ac),(v2,c),(v4,?)} {(v4,?)} v5 {(v0,ab),(v0,ac),(v0,abc),(v1,a),(v1,ab),(v2,a),(v3,b),(v5,?)} {(v5,?)} Note: (v,{Lp1,Lp2,…,Lpn}) is organized into {(v,Lp1),(v,Lp2),…,(v,Lpn)}.


本文编号：3102420