Efficient Supergraph Search Using Graph Coding
Efficient Supergraph Search Using Graph Coding
复制标题
DOI：
10.1587/transinf.2019edp7011
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Shun Imai;Akihiro Inokuchi
中科院分区：
文献类型：
--
作者：
Shun Imai;Akihiro Inokuchi
本文提出了一种搜索数据库中图形的方法，该方法由给定查询包含为子图。在提出的方法中，搜索索引不需要任何查询集或频繁的子图模式的知识。在常规技术中，列举和选择频繁的子图模式在计算上是昂贵的，并且查询集的分布必须提前知道。随后对查询集的更改需要再次选择频繁的模式，并重建索引。所提出的方法使用树结构索引克服了这些困难，该索引包含在树的浅层部分中包含不频繁的子图模式。通过遍历此代码树，我们可以快速确定数据库中的多个图是否包含匹配查询的子图，从而产生强大的修剪或过滤效果。此外，可以同时进行图形搜索的过滤和验证步骤，而不是需要单独的算法。由于所提出的方法不需要频繁的子图模式和查询集，因此它比以前的技术要快得多。与查询集的独立性还意味着，当查询集更改时，无需重建搜索索引。使用现实世界数据集的一系列实验证明了该方法的效率，搜索速度比以前的最佳速度快几个数量级。关键词：超图搜索，索引，图形编码，规范形式，子图同构
This paper proposes a method for searching for graphs in the database which are contained as subgraphs by a given query. In the proposed method, the search index does not require any knowledge of the query set or the frequent subgraph patterns. In conventional techniques, enumerating and selecting frequent subgraph patterns is computationally expensive, and the distribution of the query set must be known in advance. Subsequent changes to the query set require the frequent patterns to be selected again and the index to be reconstructed. The proposed method overcomes these difficulties through graph coding, using a tree structured index that contains infrequent subgraph patterns in the shallow part of the tree. By traversing this code tree, we are able to rapidly determine whether multiple graphs in the database contain subgraphs that match the query, producing a powerful pruning or filtering effect. Furthermore, the filtering and verification steps of the graph search can be conducted concurrently, rather than requiring separate algorithms. As the proposed method does not require the frequent subgraph patterns and the query set, it is significantly faster than previous techniques; this independence from the query set also means that there is no need to reconstruct the search index when the query set changes. A series of experiments using a real-world dataset demonstrate the efficiency of the proposed method, achieving a search speed several orders of magnitude faster than the previous best. key words: supergraph search, indexing, graph coding, canonical form, subgraph isomorphism