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

摘要

针对传统算法由于时间或空间复杂度过高而难以实现规模大且动态变化情况下标签图的Top-K子图查询问题,提出一种适用于大规模标签图的动态Top-K兴趣子图查询方法DISQtop-K.该方法建立了包括节点拓扑结构特性(NTF)索引和边特性(EF)索引的图拓扑结构特性(GTSF)索引,利用该索引可有效剪枝过滤不满足限制条件的无效节点及边;基于GTSF索引提出了多因素候选集过滤策略,通过对查询图候选集进一步剪枝以获得较少的候选集;考虑到图的动态变化可能对匹配结果产生影响,提出了Top-K兴趣子图匹配验证方法——DISQtop-K,将匹配验证过程分为初始匹配和动态修正两个阶段,以尽可能保证查询结果的实时、准确.大量实验结果表明,相比RAM、RWM算法,DISQtop-K方法的索引创建时间较短且占用空间较少,能有效处理大规模标签图中的动态Top-K兴趣子图查询.%The traditional algorithms are difficult to implement the Top-K subgraph query on large-scale dynamic labeled graph due to high time or space complexity.For this reason,a dynamic Top-K interesting subgraph query method named DISQtop-K was proposed.In this algorithm,a Graph Topology Structure Feature (GTSF) index that include Node Topology Feature (NTF) index and Edge Feature (EF) index was established,which can effectively prune and filter the invalid nodes and edges.Then a multi-factor candidate set filtering strategy was put forward based on GTSF index,which can be used to further prune the query graph candidate sets.Considering that the dynamic changes in the graph may have an impact on the matching results,to ensure the real-time and accuracy of the query results,a new matching-verification method for Top-K interesting subgraph was also given,which has two stages of initial matching and dynamic correction.Experimental results show that compared with RAM and RWM,DISQtop-K method costs shorter time for index creation and occupies less space,which can effectively deal with dynamic Top-K interesting subgraph query on large-scale labeled graph.