• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Proof of Designed Reliability >Efficient algorithms for pattern matching on directed acyclic graphs
【24h】

Efficient algorithms for pattern matching on directed acyclic graphs

机译：用于有向无环图的模式匹配的高效算法

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

摘要

Recently graph data models have become increasingly popular in many scientific fields. Efficient query processing over such data is critical. Existing works often rely on index structures that store pre-computed transitive relations to achieve efficient graph matching. In this paper, we present a family of stack-based algorithms to handle path and twig pattern queries for directed acyclic graphs (DAGs) in particular. With the worst-case space cost linearly bounded by the number of edges in the graph, our algorithms achieve a quadratic runtime complexity in the average size of the query variable bindings. This is optimal among the navigation-based graph matching algorithms.
机译：最近，图数据模型已在许多科学领域变得越来越流行。对此类数据进行有效的查询处理至关重要。现有作品通常依赖于存储预先计算的传递关系的索引结构，以实现有效的图形匹配。在本文中，我们提出了一系列基于堆栈的算法，尤其是针对有向无环图（DAG）的路径和嫩枝模式查询。由于最坏情况下的空间成本受图中边数的线性限制，我们的算法在查询变量绑定的平均大小上实现了二次运行时复杂性。在基于导航的图匹配算法中，这是最佳的。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号