-
题名层次序列索引的大规模动态标签图子图查询
被引量：1
- 1
-
-
作者
任成林
姜丽雁
单晓欢
宋宝燕
-
机构
辽宁大学信息学院
-
出处
《计算机工程与应用》
CSCD
北大核心
2019年第1期70-75,共6页
-
基金
国家自然科学基金(No.61472169
No.61502215)
+2 种基金
辽宁省教育厅一般项目(No.L2015193)
辽宁省教育厅科学研究项目(No.LYB201617)
辽宁省博士科研启动基金(No.201501127)
-
文摘
标签图常用于智能交通网、生物信息网等新兴领域的建模。子图查询作为图数据分析的关键问题,引起了研究者的广泛关注。对现有子图查询算法的研究发现,随着图数据规模增大且频繁更新,传统子图查询算法普遍存在查询效率低,存储开销大,忽略顶点标签信息等问题。为此,提出了一种支持大规模动态标签图子图查询的层次序列索引(Dynamic Hierarchical Sequence,DHS),该索引提取数据图中带有顶点编号的层次拓扑序列关系以实现子图查询;针对图的动态变化,提出了更新点拓扑扩展式索引维护策略,仅从局部变化顶点及边开始进行增量式更新,大大降低了重建索引造成的巨大开销;提出了基于DHS索引的子图查询方法,仅需将查询图与数据图的层次序列进行匹配即可获得候选集,并在其上利用关系匹配策略获得最终查询结果。实验证明提出的方法在保证高效查询的同时降低了索引的创建及维护时间,提高了子图查询效率。
-
关键词
大规模动态标签图
子图查询
层次拓扑序列
图索引
-
Keywords
large-scale dynamic labeled graph
subgraph query
topological hierarchical sequence
graph index
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
