大规模动态标签图Top-K兴趣子图查询方法研究

发布时间：2021-10-19 10:40

　　标签图是指节点具有标识能力的一种特殊的图结构,已经普遍应用于地理社交网络、电子商务网络以及生物信息网络等领域的建模。随着科学与计算机技术飞速发展,上述各领域抽象的标签图除具有传统的图数据特点外,又呈现了数据规模巨大、数据增长过快以及数据更新频繁等特点。子图查询因对图数据分析具有重要意义得到了研究者的广泛研究。然而,随着标签图规模日益增大,人们逐渐倾向于只关注众多查询结果中一些高匹配结果,希望借助查询结果之间的关系以及数量等快速获取期望结果。因而,为了满足用户的个性化查询需求,更具针对性的Top-K兴趣子图查询方法应运而生。研究者考虑到传统的无优化策略的子图查询算法在大规模图中难以应用的弊端,研究借助数据库的索引技术实现对图中节点或边进行索引,或借助图压缩技术缩减数据图规模以加快查询效率。然而,大多数新研究的子图查询算法忽略了现阶段的大部分标签图的数据增长过快以及数据更新过于频繁的特点。同时,在Top-K兴趣子图查询中,多借助边的权值定义实体间的某种限制关系,这导致现有的针对无权图的子图查询算法难以直接应用。因而如何实现在大规模且动态变化的加权标签图上的Top-K兴趣子图查询成为图数据处... 

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

【文章页数】：71 页

【学位级别】：硕士

【部分图文】：

索引构建时间及存储开销

各算法查询时间对比

第 5 章 实验与分析图 5-3(a)展示了在真实数据集 Youtube 上，随着查询图规模 Q 的增加各算法查询时间的对比情况。因为 RAM 和 RWM 算法在利用路径过滤后，需要再次对比每个匹配中各边的权值，因此，随着查询图规模的增大，RAM 与 RWM 算法查询时间会显著增加。相比而言，DISQtop-K 与 PSM 算法随着查询图规模的增加，查询时间的增加会比较平缓。又因为查询图规模越大，因压缩而被过滤的节点与边越多，因此 DISQtop-K 算法在查询图规模较大时，会更有利。图 5-3(b)展示了在真实数据集 DBLP 上，随着查询图规模和 K 值的增大，DISQtop-K 算法查询时间的变化情况。由图可知，随着查询图规模的增加，DISQtop-K 算法的查询时间有所增加，但增加相对平缓。当查询图 Q 固定时，K 值变化时，查询图的波动较小。图 5-3 验证了 DISQtop-K 算法有较好的可扩展性。

【参考文献】：
期刊论文
[1]一种基于自适应结构概要的有向标签图子图匹配查询算法[J]. 张海威,解晓芳,段媛媛,温延龙,张莹,袁晓洁.  计算机学报. 2017(01)
[2]大规模数据图上的个性化子图匹配算法[J]. 杨艳,纪安娜,金虎.  计算机研究与发展. 2015(S1)
[3]不确定图数据库中高效查询处理[J]. 张硕,高宏,李建中,邹兆年.  计算机学报. 2009(10)
[4]不确定性数据管理技术研究综述[J]. 周傲英,金澈清,王国仁,李建中.  计算机学报. 2009(01)
[5]基于滑动窗口的数据流连续J-A查询的处理方法[J]. 王伟平,李建中,张冬冬,郭龙江.  软件学报. 2006(04)



本文编号：3444716