节点与决策模式两段式映射的子图查询算法

摘要：

针对大规模图集的子图查询问题,给出了一种基于节点与决策模式映射(NDFM)的索引结构--NDFM-Index,并在此索引结构的基础上提出了一种图集的子图查询算法.NDFM-Index利用图中关键节点所携带的结构信息以及邻居的标号分布,与决策模式形成映射,从而不通过枚举直接得到查询图所包含的索引模式,得到更小的候选集.理论与实验的分析结果表明,该算法不但能避免索引筛选过程中对查询图子图的枚举过程,而且能显著地减小候选集尺寸,进而大大降低查询图与候选集之间的子图同构测试次数,提高查询效率.

关键词：图数据集、图查询、频繁模式、决策模式、节点向量

所属期刊栏目：20

分类号：TP1;TN9

资助基金：国家自然科学基金60773063,60473075,60533110,60803036;973计划2006CB303000

在线出版日期：2010-05-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：270-278