• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE transactions on industrial informatics >Efficient and Exact Multigraph Matching Search
【24h】

Efficient and Exact Multigraph Matching Search

机译：高效和精确的多金属匹配搜索

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：多密码作为图形袋子建模。精确的Multigraph匹配搜索旨在找到与数据多字数据集相同的所有多层游文。据我们所知，虽然它们具有非常广泛的应用方案，但尚未报告有关确切的MultikaPh匹配搜索的作品。在本文中，我们提出了一种有效的算法来解决精确的多密码匹配搜索问题。我们首先提出了一种定义了精确的多核匹配及其称为BM的基本方法（BM），其具有相当大量的图形同构检测计算，因此具有非常高的计算复杂性。显然，将查询多密码与Multigraph数据集中的每个数据多密码进行比较是不切实际的。为了减少搜索空间，提出了多个过滤条件以获得包含所有最终结果的候选结果集，包括基数滤波器，顶点滤波器，边缘滤波器，尺寸过滤器和星形过滤器。然后，用改进的BM（IBM）算法验证候选结果集中的每个多密码。此外，提出了名为MII的离线和多层反相指数（MII），以进一步加速搜索过程。最后，我们提出了一种基于上述技术的精确的多密码匹配搜索（EMMS）算法。我们还分析了其时间复杂性。实际数据集的广泛实验证明了所提出的算法的有效性和效率。

著录项

  • 来源
    《IEEE transactions on industrial informatics》 |2021年第6期|4141-4149|共9页
  • 作者

    Pang Jun; Shu Zhiliang; Ding Linlin; Jiang Chengyang; Liu Chen; Zhang Xiaolong;

  • 作者单位

    Wuhan Univ Sci & Technol Sch Comp Sci & Technol Hubei Key Lab Intelligent Informat Proc & Realtim Inst Big Data Sci & Engn Wuhan 430065 Hubei Peoples R China;

    Wuhan Univ Sci & Technol Sch Comp Sci & Technol Hubei Key Lab Intelligent Informat Proc & Realtim Inst Big Data Sci & Engn Wuhan 430065 Hubei Peoples R China;

    Liaoning Univ Sch Informat Shenyang 110036 Peoples R China;

    Wuhan Univ Sci & Technol Sch Comp Sci & Technol Hubei Key Lab Intelligent Informat Proc & Realtim Inst Big Data Sci & Engn Wuhan 430065 Hubei Peoples R China;

    Wuhan Univ Sci & Technol Sch Comp Sci & Technol Hubei Key Lab Intelligent Informat Proc & Realtim Inst Big Data Sci & Engn Wuhan 430065 Hubei Peoples R China;

    Wuhan Univ Sci & Technol Sch Comp Sci & Technol Hubei Key Lab Intelligent Informat Proc & Realtim Inst Big Data Sci & Engn Wuhan 430065 Hubei Peoples R China;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    Search problems; Indexes; Drugs; Nonhomogeneous media; Informatics; Roads; Smart cities; Exact match; index; multigraph; smart city;

    机译：搜索问题;索引;毒品;非均匀媒体;信息学;道路;智能城市;完全匹配;指数;多角形;智能城市;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号