• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Graph-based representations in pattern recognition >Indexing with Weil-Founded Total Order for Faster Subgraph Isomorphism Detection
【24h】

Indexing with Weil-Founded Total Order for Faster Subgraph Isomorphism Detection

机译：使用Weil建立的总顺序建立索引，以更快地进行子图同构检测

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper an extension of index-based subgraph matching is proposed. This extension significantly reduces the storage amount and indexing time for graphs where the nodes are labeled with a rather small amount of different classes. In order to reduce the number of possible permutations, a weight function for labeled graphs is introduced and a well-founded total order is defined on the weights of the labels. Inversions which violate the order are not allowed. A computational complexity analysis of the new preprocessing is given and its completeness is proven. Furthermore, in a number of practical experiments with randomly generated graphs the improvement of the new approach is shown. In experiments performed on random sample graphs, the number of permutations has been decreased to a fraction of 10~-18 in average compared to the original approach by Messmer. This makes indexing of larger graphs feasible, allowing for fast detection of subgraphs.
机译：本文提出了基于索引的子图匹配的扩展。此扩展显着减少了图的存储量和索引时间，在图上用很少量的不同类标记节点。为了减少可能的排列数量，引入了带标签图的权重函数，并在标签的权重上定义了有充分根据的总顺序。不允许违反顺序的反转。给出了新预处理的计算复杂度分析，并证明了其完整性。此外，在许多随机生成的图的实际实验中，显示了新方法的改进。在随机样本图上进行的实验中，与Messmer的原始方法相比，排列的数量平均减少了10〜-18％。这使得对较大图形的索引成为可能，从而可以快速检测子图形。

著录项

  • 来源
  • 会议地点 Munster(DE);Munster(DE)
  • 作者

    Markus Weber; Marcus Liwicki; Andreas Dengel;

  • 作者单位

    Knowledge Management Department, German Research Center for Artificial Intelligence (DFKI) GmbH Trippstadter Straße 122, 67663 Kaiserslautern, Germany , Knowledge-Based Systems Group, Department of Computer Science, University of Kaiserslautern, P.O. Box 3049, 67653 Kaiserslautern;

    Knowledge Management Department, German Research Center for Artificial Intelligence (DFKI) GmbH Trippstadter Straße 122, 67663 Kaiserslautern, Germany , Knowledge-Based Systems Group, Department of Computer Science, University of Kaiserslautern, P.O. Box 3049, 67653 Kaiserslautern;

    Knowledge Management Department, German Research Center for Artificial Intelligence (DFKI) GmbH Trippstadter Straße 122, 67663 Kaiserslautern, Germany , Knowledge-Based Systems Group, Department of Computer Science, University of Kaiserslautern, P.O. Box 3049, 67653 Kaiserslautern;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 信息处理（信息加工）;
  • 关键词

    graph isomorphism; subgraph isomorphism; tree search; decision tree; indexing.;

    机译：图同构子图同构树搜索；决策树;索引。;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号