大规模标签图中的动态Top-K兴趣子图查询

作者：宋宝燕; 贾春杰; 单晓欢; 丁琳琳; 丁兴艳

来源：计算机应用, 2018, 38(02): 471-477.

• 大规模标签图
• 动态Top-K
• 兴趣子图
• 子图查询

针对传统算法由于时间或空间复杂度过高而难以实现规模大且动态变化情况下标签图的Top-K子图查询问题,提出一种适用于大规模标签图的动态Top-K兴趣子图查询方法 DISQtop-K。该方法建立了包括节点拓扑结构特性(NTF)索引和边特性(EF)索引的图拓扑结构特性(GTSF)索引,利用该索引可有效剪枝过滤不满足限制条件的无效节点及边;基于GTSF索引提出了多因素候选集过滤策略,通过对查询图候选集进一步剪枝以获得较少的候选集;考虑到图的动态变化可能对匹配结果产生影响,提出了Top-K兴趣子图匹配验证方法——DISQtop-K,将匹配验证过程分为初始匹配和动态修正两个阶段,以尽可能保证查询结果的实时、准确。大量实验结果表明,相比RAM、RWM算法,DISQtop-K方法的索引创建时间较短且占用空间较少,能有效处理大规模标签图中的动态Top-K兴趣子图查询。

• 出版日期2018
• 单位辽宁大学