| 李先通,李建中.节点与决策模式两段式映射的子图查询算法[J].高技术通讯(中文),2010,20(3):270~278 |
| 节点与决策模式两段式映射的子图查询算法 |
| A subgraph query algorithm based on two step mapping on vertex to decision feature |
| |
| DOI： |
| 中文关键词: 图数据集， 图查询， 频繁模式， 决策模式， 节点向量 |
| 英文关键词: graph dataset, graph query, frequent feature, decision feature, vertex array |
| 基金项目:国家自然科学基金(60773063，60473075，60533110，60803036)和973计划(2006CB303000)资助项目 |
| 作者 | 单位 | | 李先通 | 哈尔滨工业大学计算机科学与技术学院 | | 李建中 | 哈尔滨工业大学计算机科学与技术学院 |
|
| 摘要点击次数: 2717 |
| 全文下载次数: 2126 |
| 中文摘要: |
| 针对大规模图集的子图查询问题，给出了一种基于节点与决策模式映射(NDFM)的索引结构——NDFM Index，并在此索引结构的基础上提出了一种图集的子图查询算法。NDFM Index利用图中关键节点所携带的结构信息以及邻居的标号分布，与决策模式形成映射，从而不通过枚举直接得到查询图所包含的索引模式，得到更小的候选集。理论与实验的分析结果表明,该算法不但能避免索引筛选过程中对查询图子图的枚举过程,而且能显著地减小候选集尺寸,进而大大降低查询图与候选集之间的子图同构测试次数,提高查询效率。 |
| 英文摘要: |
| To solve the problem of subgraph query processing in large graph databases, the paper gives a two step node to decision feature mapping (NDFM) indexed structure，named the NDFM Index, and based on it, proposes a subgraph query processing algorithm. The NDFM Index uses the mapping between key nodes, with the distribution of neighbors labels, and decision features to get the indexed features which are included by query graph avoiding enumeration method. The results of theoretical analysis and experimental evaluation show that the proposed method not only avoids the enumeration method of getting subgraphs of query graph, but also effectively reduces the subgraph isomorphism tests between the query graph and graphs in candidate answer set in verification stage. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
|
|
|
