大规模标签图中的动态Top-K兴趣子图查询
来源：计算机应用杂志2018年第2期北京时间：
作者：宋宝燕, 贾春杰, 单晓欢, 丁琳琳, 丁兴艳
单位：辽宁大学 信息学院, 沈阳 110036
摘要：针对传统算法由于时间或空间复杂度过高而难以实现规模大且动态变化情况下标签图的Top-K子图查询问题，提出一种适用于大规模标签图的动态Top-K兴趣子图查询方法DISQtop-K。该方法建立了包括节点拓扑结构特性（NTF）索引和边特性（EF）索引的图拓扑结构特性（GTSF）索引，利用该索引可有效剪枝过滤不满足限制条件的无效节点及边；基于GTSF索引提出了多因素候选集过滤策略，通过对查询图候选集进一步剪枝以获得较少的候选集；考虑到图的动态变化可能对匹配结果产生影响，提出了Top-K兴趣子图匹配验证方法——DISQtop-K，将匹配验证过程分为初始匹配和动态修正两个阶段，以尽可能保证查询结果的实时、准确。大量实验结果表明，相比RAM、RWM算法，DISQtop-K方法的索引创建时间较短且占用空间较少，能有效处理大规模标签图中的动态Top-K兴趣子图查询。
关键词：大规模标签图,动态Top-K,兴趣子图,子图查询
基金资助：国家自然科学基金资助项目（61472169，61502215）；国家重点研发计划项目（2016YFC0801406）；辽宁省教育厅一般项目（L2015193）；辽宁省博士科研启动基金项目（201501127）。
