大规模动态有向标签图子图查询方法研究

发布时间：2022-01-03 18:24

　　随着计算机应用领域的丰富与扩展,图作为常用的数据结构之一,现实世界的诸多领域均用图来描述其复杂而庞大的逻辑关系,如社交网、生物信息网、智能交通网等新兴领域的建模。同时在某些复杂网络中存在多种类别的顶点,常利用标签图对此类复杂网络进行建模。如社交网中的微博,我们可以用顶点表示微博用户,任意用户之间的关注情况可通过有向边来表示,此时标签可用来表示用户的性别、所在地、关注领域等信息。子图查询作为图数据分析的关键问题,引起了研究者的广泛关注。动态标签图子图查询,即返回结构及标签值均同构于查询图的若干子图。然而子图同构查询是一个NP完全问题,随着数据图的增长且频繁更新,查询时间会大大增加,通过创建高质量的索引结构以提高查询效率已成为解决这一问题的关键。例如:微博新用户的注册、老用户的注销、用户间新增或取消关注等行为都会导致标签图的动态变化。微博应用中新用户注册、用户添加关注等行为都将抽象为标签图顶点或边的插入,微博中用户账号注销,取消关注等行为都将抽象为标签图中顶点或边的删除。对现有子图查询算法的研究发现,随着图数据规模增大且频繁更新,传统子图查询算法普遍存在查询效率低、存储开销大、忽略顶点标签... 

【文章来源】：辽宁大学辽宁省 211工程院校

【文章页数】：63 页

【学位级别】：硕士

【部分图文】：

索引创建时间

43图（f）图 5-3 查询操作执行时间 本章小结通过上述实验结果可知，本文提出的支持动态有向标签图的子图查询方大规模动态有向标签图的分布式子图查询方法是都是有效可行的，两种引构造简单且索引体积较小，更新时间短，该查询方法在频繁更新的动上表现出良好的查询性能，并且时间和空间代价都很小。

【参考文献】：
期刊论文
[1]基于增量信息索引的子图查询算法[J]. 王超珲,黄一夫.  计算机应用与软件. 2016(10)
[2]一种面向动态连续查询的查询索引[J]. 邓泽,刘汪洋,陈丹.  计算机应用与软件. 2015(12)
[3]一种基于自适应结构概要的有向标签图子图匹配查询算法[J]. 张海威,解晓芳,段媛媛,温延龙,张莹,袁晓洁.  计算机学报. 2017(01)
[4]大规模数据图上的个性化子图匹配算法[J]. 杨艳,纪安娜,金虎.  计算机研究与发展. 2015(S1)
[5]支持动态图数据的子图查询方法[J]. 王楠,王斌,李晓华,杨晓春.  计算机科学与探索. 2014(02)
[6]不确定数据频繁项集挖掘方法综述[J]. 汪金苗,张龙波,邓齐志,王凤英,王勇.  计算机工程与应用. 2011(20)



本文编号：3566754