skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

Efficient Graph Similarity Search Over Large Graph Databases

Zheng, Weiguo ; Zou, Lei ; Lian, Xiang ; Wang, Dong ; Zhao, Dongyan

IEEE transactions on knowledge and data engineering, 2015-04, Vol.27 (4), p.964-978 [Periódico revisado por pares]

New York: IEEE

Texto completo disponível

Citações Citado por
  • Título:
    Efficient Graph Similarity Search Over Large Graph Databases
  • Autor: Zheng, Weiguo ; Zou, Lei ; Lian, Xiang ; Wang, Dong ; Zhao, Dongyan
  • Assuntos: Chemicals ; Compounds ; Graph matching ; Graphs ; Heuristic ; Indexes ; Lower bounds ; Partitioning algorithms ; Pruning ; Query processing ; Search problems ; Searching ; Similarity ; Transforms
  • É parte de: IEEE transactions on knowledge and data engineering, 2015-04, Vol.27 (4), p.964-978
  • Notas: ObjectType-Article-1
    SourceType-Scholarly Journals-1
    ObjectType-Feature-2
    content type line 23
  • Descrição: Since many graph data are often noisy and incomplete in real applications, it has become increasingly important to retrieve graphs g in the graph database D that approximately match the query graph q, rather than exact graph matching. In this paper, we study the problem of graph similarity search, which retrieves graphs that are similar to a given query graph under the constraint of graph edit distance. We propose a systematic method for edit-distance based similarity search problem. Specifically, we derive two lower bounds, i.e., partition-based and branch-based bounds, from different perspectives. More importantly, a hybrid lower bound incorporating both ideas of the two lower bounds is proposed, which is theoretically proved to have higher (at least not lower) pruning power than using the two lower bounds together. We also present a uniform index structure, namely u-tree, to facilitate effective pruning and efficient query processing. Extensive experiments confirm that our proposed approach outperforms the existing approaches significantly, in terms of both the pruning power and query response time.
  • Editor: New York: IEEE
  • Idioma: Inglês
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.