.png){kind=icon}
返回
Efficient and Exact Multigraph Matching Search
.png){kind=icon}
PRE
AI
DOI：10.1109/TII.2020.3013273.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
A multigraph is modeled as a bag of graphs. Exact multigraph matching search aims to find all multigraphs that are the same as the query multigraphs from the data multigraph datasets. To the best of our knowledge, works regarding exact multigraph matching search have not been reported although they have a very wide range of application scenarios. In this article, we propose an efficient algorithm to solve the problem of exact multigraph matching search. We first propose a definition of exact multigraph matching and its Basic Method (BM), called BM, which has a considerable amount of graph isomorphism detection calculations and, thus, has very high computational complexity. Obviously, it is impractical to compare the query multigraph to each data multigraph in the multigraph datasets. To reduce the search space, multiple filtering conditions are proposed to obtain a candidate result set containing all the final results, including the cardinality filter, the vertex filter, the edge filter, the size filter, and the star filter. Then, each multigraph in the candidate result set is verified with the Improved BM (IBM) algorithm. Moreover, an offline and Multilayer Inverted Index (MII), named MII, is proposed to further accelerate the search process. Finally, we propose an Exact Multigraph Matching Search (EMMS) algorithm, based on the abovementioned technologies. We also analyze its time complexity. Extensive experiments on real datasets demonstrate the effectiveness and efficiency of the proposed algorithms.
Keyword:
Search problems
Indexes
Drugs
Nonhomogeneous media
Informatics
Roads
Smart cities
Exact match
index
multigraph
smart city
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
9.9
论文数:
8.6K
被引数:
6.0W
机构
引用论文
Effective and Efficient Dense Subgraph Query in Large-Scale Social Internet of Things大规模社交物联网中高效密集子图查询
PREAI
分享收藏Semi-supervised multi-graph classification using optimal feature selection and extreme learning machine基于最优特征选择和极限学习机的半监督多图分类.png)
NEUROCOMPUTING
NEUROCOMPUTINGIF6.5
PREAI
分享收藏Health Literacy – a review of research using the European Health Literacy Questionnaire (HLS-EU-Q16) in 2010-2018健康素养-2010-2018使用欧洲健康素养问卷 (HLS-EU-Q16) 进行的研究综述
OAAI
OAAI分享收藏
查看更多内容