面向子图同构的高效索引构建算法

面向子图同构的高效索引构建算法

论文摘要

针对子图同构中索引构建方法效率低、内存占用大而影响查询效率的问题,本文提出基于2次排序查找等价顶点的数据图索引构建算法。该算法采用不同邻接链表表示类别不同的语法等价顶点的邻居集合,并依此设计2次排序的方法快速查找数据图中两两互连和两两互不相连的等价顶点,然后依据语法等价和语法包含关系为数据图构建索引来提高子图同构查询的效率。最后,基于不同规模的数据集,通过实验验证了本文提出索引构建算法的高效性和可扩展性。

论文目录

  • 1 子图同构相关概念
  • 2 高效的数据图索引构建方法
  •   2.1 问题分析
  •   2.2 基本思想
  •   2.3 算法描述
  •   2.4 算法分析
  •     2.4.1 时间复杂度
  •     2.4.2 空间复杂度
  • 3 基于实际数据集的实验比较
  •   3.1 实验环境
  •   3.2 数据集
  •   3.3 性能比较与分析
  •     3.3.1 超图索引的构建时间
  •     3.3.2 内存占用情况
  • 4 结论
  • 文章来源

    类型: 期刊论文

    作者: 陈伟,李美云,陈子阳,罗雅琴

    关键词: 子图同构,图索引,语法等价,语法包含,超图,排序

    来源: 哈尔滨工程大学学报 2019年03期

    年度: 2019

    分类: 工程科技Ⅱ辑,基础科学,信息科技

    专业: 数学,计算机软件及计算机应用

    单位: 燕山大学信息科学与工程学院,河北环境工程学院信息工程系,上海工程技术大学数理与统计学院

    基金: 国家自然科学基金项目(61472339,61572421)

    分类号: TP311.13;O157.5

    页码: 548-554

    总页数: 7

    文件大小: 3037K

    下载量: 77

    相关论文文献

    • [1].基于对称破坏的子图同构约束求解算法[J]. 计算机工程与设计 2020(02)
    • [2].不确定属性图的子图同构及其判定算法[J]. 计算机科学 2013(06)
    • [3].不确定图间α-β子图同构匹配算法[J]. 智能计算机与应用 2011(05)
    • [4].图同构的判定研究[J]. 集成技术 2013(06)
    • [5].一种多到一子图同构检测方法[J]. 软件学报 2010(03)
    • [6].基于关系模型的子图同构检测算法设计与实现[J]. 计算机工程 2011(11)
    • [7].无向图同构的判定研究[J]. 软件 2018(11)
    • [8].一种无向图同构的判定算法[J]. 科技创新与应用 2012(28)
    • [9].无向图同构的快速算法[J]. 华南理工大学学报(自然科学版) 2011(10)
    • [10].图同构的一个充分必要条件[J]. 计算机工程与应用 2009(30)
    • [11].图同构的零知识证明协议[J]. 中北大学学报(自然科学版) 2014(03)
    • [12].基于符号OBDD的子图同构约束求解算法[J]. 桂林电子科技大学学报 2019(05)
    • [13].一种求解子图同构问题的改进遗传算法[J]. 计算机科学 2019(S1)
    • [14].图同构的充要条件[J]. 西南民族大学学报(自然科学版) 2011(05)
    • [15].图同构判定的新方法[J]. 河北理工大学学报(自然科学版) 2008(01)
    • [16].基于子图结点度数相异的图同构判定方法[J]. 计算机与现代化 2013(04)
    • [17].基于子图同构的三维CAD模型局部匹配[J]. 计算机辅助设计与图形学学报 2008(08)
    • [18].基于子图同构的三维CAD模型局部匹配探讨[J]. 电脑知识与技术 2016(13)
    • [19].基于子图同构的可配置产品功能结构特征模板相似性获取[J]. 计算机集成制造系统 2009(09)
    • [20].甲骨文识别的图同构方法[J]. 计算机工程与应用 2011(08)
    • [21].URSI:高效的子图同构查询算法[J]. 燕山大学学报 2016(06)
    • [22].无向无权图同构判别算法[J]. 西南师范大学学报(自然科学版) 2017(03)
    • [23].一种新的改进的判定图同构的遗传算法[J]. 云南师范大学学报(自然科学版) 2013(01)
    • [24].基于状态转换图同构求解的等价性验证算法[J]. 计算机技术与发展 2009(03)
    • [25].图同构的必要条件[J]. 大学数学 2012(06)
    • [26].基于子图同构的煤矿通风系统高风险区域识别[J]. 煤炭科学技术 2018(11)
    • [27].遗传算法在图同构判定中的应用与实现[J]. 硅谷 2010(20)
    • [28].基于GPU的RDF类型同构并行算法[J]. 计算机研究与发展 2018(03)
    • [29].无向图同构的充要条件以及判定[J]. 佳木斯大学学报(自然科学版) 2015(02)
    • [30].基于子图同构的vEPC虚拟网络分层协同映射算法[J]. 电子与信息学报 2017(05)

    标签:;  ;  ;  ;  ;  ;  

    面向子图同构的高效索引构建算法
    下载Doc文档

    猜你喜欢