A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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

Efficient Supergraph Search Using Graph Coding Pesquisa eficiente de supergráficos usando codificação gráfica

Shun IMAI, Akihiro INOKUCHI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

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.

Publicação
IEICE TRANSACTIONS on Information Vol.E103-D No.1 pp.130-141
Data de publicação
2020/01/01
Publicitada
2019/09/26
ISSN online
1745-1361
DOI
10.1587/transinf.2019EDP7011
Tipo de Manuscrito
PAPER
Categoria
Engenharia de Dados, Sistemas de Informação Web

autores

Shun IMAI
  Kwansei Gakuin University
Akihiro INOKUCHI
  Kwansei Gakuin University

Palavra-chave