文章基本信息

标题：An Intelligent System for Subgraph Matching with Set Similarity in Large Graph Database
本地全文：下载
作者：Monali Vitthal Divekar ; Prof. Shyam S. Gupta
期刊名称：International Journal of Innovative Research in Science, Engineering and Technology
印刷版ISSN：2347-6710
电子版ISSN：2319-8753
出版年度：2017
卷号：6
期号：5
页码：9959
DOI：10.15680/IJIRSET.2017.0605342
出版社：S&S Publications
摘要：In real lifestyles, interpersonal companies, Semantic internet and Natural techniques, social networks,and biological networks, each vertex extra by and large than now not contains important information, which may alsobe displayed by way of an arrangement of tokens or components. In this paper, a subgraph matching with set similarity(SMS2) query over a large graph database, which retrieves subgraphs that are structurally isomorphic to the querygraph, and during this time period it also satisfy the condition of vertex pair matching with the (dynamic) weighted setsimilarity. This paper designs a novel lattice-based index for data graph to efficiently process the SMS2 query, andlightweight signatures for both query and data vertices. We not only propose an efficient two-phase pruning strategybased on the index and signatures, which including set similarity pruning and structure-based pruning, and also utilizesthe unique features of both (dynamic) weighted set similarity and graph topology, but also propose an efficientdominating-set-based subgraph matching algorithm direct by a dominating set selection algorithm to achieve betterquery performance. Extensive experiments on both real as well as synthetic datasets demonstrate that our methodoutperforms state of-the-art methods by order of magnitude.
关键词：subgraph matching; graph database; pruning strategy; vertex pair matching; weighted set similarity;query processing; SMS2 query; dynamic set similarity; structurally isomorphic subgraph; synthetic datasets.