The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Este artigo propõe um método para busca de gráficos no banco de dados que estão contidos como subgráficos por uma determinada consulta. No método proposto, o índice de pesquisa não requer nenhum conhecimento do conjunto de consultas ou dos padrões frequentes de subgráficos. Nas técnicas convencionais, enumerar e selecionar padrões de subgrafos frequentes é computacionalmente caro, e a distribuição do conjunto de consultas deve ser conhecida antecipadamente. Alterações subsequentes no conjunto de consultas exigem que os padrões frequentes sejam selecionados novamente e o índice seja reconstruído. O método proposto supera essas dificuldades através da codificação de grafos, utilizando um índice estruturado em árvore que contém padrões de subgráficos pouco frequentes na parte rasa da árvore. Ao percorrer essa árvore de código, podemos determinar rapidamente se vários gráficos no banco de dados contêm subgráficos que correspondem à consulta, produzindo um efeito poderoso de remoção ou filtragem. Além disso, as etapas de filtragem e verificação da pesquisa gráfica podem ser conduzidas simultaneamente, em vez de exigir algoritmos separados. Como o método proposto não requer padrões de subgráficos frequentes e conjunto de consultas, ele é significativamente mais rápido que as técnicas anteriores; essa independência do conjunto de consultas também significa que não há necessidade de reconstruir o índice de pesquisa quando o conjunto de consultas muda. Uma série de experimentos usando um conjunto de dados do mundo real demonstra a eficiência do método proposto, alcançando uma velocidade de busca várias ordens de magnitude mais rápida que a melhor anterior.
Shun IMAI
Kwansei Gakuin University
Akihiro INOKUCHI
Kwansei Gakuin University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Shun IMAI, Akihiro INOKUCHI, "Efficient Supergraph Search Using Graph Coding" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 1, pp. 130-141, January 2020, doi: 10.1587/transinf.2019EDP7011.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019EDP7011/_p
Copiar
@ARTICLE{e103-d_1_130,
author={Shun IMAI, Akihiro INOKUCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Efficient Supergraph Search Using Graph Coding},
year={2020},
volume={E103-D},
number={1},
pages={130-141},
abstract={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.},
keywords={},
doi={10.1587/transinf.2019EDP7011},
ISSN={1745-1361},
month={January},}
Copiar
TY - JOUR
TI - Efficient Supergraph Search Using Graph Coding
T2 - IEICE TRANSACTIONS on Information
SP - 130
EP - 141
AU - Shun IMAI
AU - Akihiro INOKUCHI
PY - 2020
DO - 10.1587/transinf.2019EDP7011
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2020
AB - 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.
ER -