基于非易失存储器的子图匹配算法研究

发布时间：2020-09-27 19:33

　　 随着计算机存储器技术的发展,近年来出现了一类新型存储器—按字节寻址非易失存储器(byte-addressable non-volatile memory),简称NVM。NVM融合了传统DRAM按字节寻址和传统外存非易失的特点,有望在将来成为计算机存储结构层次的重要组成部分。然而,由于NVM的读写不对称性,现有的内存算法可能不再适用。基于这一背景,本文着重研究了在NVM上的高效子图匹配算法问题。本文的主要研究内容分为以下几个方面:首先研究了基于NVM的高效精确子图匹配算法。由于对NVM进行一次写的代价显著高于其读代价,因此算法的关键在于用以一定的读操作为代价来尽量减少写操作的次数,从而提高算法的运行效率。本文通过对现有算法的定性和定量分析,找到了现有算法涉及较多写次数的关键部分,并提出了一种新的数据结构ILD表以减少匹配过程中的写操作次数,解决了传统回溯算法的写操作数量过多的问题,从而提高算法在NVM上的性能。其次在上述算法的基础之上研究在NVM上基于动态图更新的高效子图匹配算法。本文改进了IDL表的存储结构,使得在图更新时带来的写操作次数尽可能少,更新代价尽可能小;另一方面本文提出了一种对更新结果出现区域的限制策略,减少更新算法的搜索空间大小,从而提高算法的运行效率。然后基于传统的近似子图匹配算法研究在NVM上高效的近似算法,研究能否以较少的精确性损失为代价进一步提高算法的效率。本文提出了基于双向模拟的子图匹配问题的定义,解决了传统基于模拟的定义带来的顶点错配问题,并基于这一定义,通过限制现有算法对辅助索引的建立,提出了两个在NVM上的高效算法。最后对于本文提出的算法进行了具体的实现,并通过基于仿真平台的实验,比较了本文提出的各类算法和传统算法在NVM上的运行效率。实验结果表明本文提出的算法相对现有算法在运行效率上有显著的提升。
【学位单位】：哈尔滨工业大学
【学位级别】：硕士
【学位年份】：2017
【中图分类】：TP391.41;TP333
【部分图文】：

图 2-2 基本回溯算法举例例给出一个基于回溯算法框架进行子图匹配尝试图，图 2-1(b)为数据图。假设匹配顺序为 1, ， 的候选顶点集为 , 。一开始 被匹配

算法在DRAM和NVM上性能对比

图 3-2 通过 ILD 表获取候选顶点集图 3-2(b)是一个数据图，图 3-2(a)是其对应的 ILD 表。图 3-2(c)是待假设现在需要获取查询图顶点 1的候选顶点集。 1的标签为 A，在

【参考文献】

相关期刊论文 前10条

1 余靖;韩玉;;URSI:高效的子图同构查询算法[J];燕山大学学报;2016年06期

2 张海威;解晓芳;段媛媛;温延龙;张莹;袁晓洁;;一种基于自适应结构概要的有向标签图子图匹配查询算法[J];计算机学报;2017年01期

3 蔡涛;张永春;牛德姣;倪晓蓉;梁东莺;;面向新型非易失存储器的文件级磨损均衡机制[J];计算机研究与发展;2015年07期

4 陈东;王波;席耀一;唐浩浩;;基于邻居向量的近似子图匹配[J];计算机工程与设计;2014年11期

5 蔡涛;张永春;倪晓蓉;牛德姣;梁东莺;周东明;;面向非易失存储器外存系统的缓存机制[J];小型微型计算机系统;2014年09期

6 黄云;洪佳明;覃遵跃;;大型网络中近似子图匹配研究[J];计算机工程;2012年18期

7 张一楠;邹兆年;李建中;;不确定图间α-β子图同构匹配算法[J];智能计算机与应用;2011年05期

8 张一楠;高宏;张炜;;基于双分支特征编码的子图查询处理算法[J];计算机研究与发展;2011年S3期

9 张硕;李建中;高宏;邹兆年;;一种多到一子图同构检测方法[J];软件学报;2010年03期

10 张志祥;李庆华;罗建明;;改进的基于分解的子图同构算法[J];计算机科学;2006年01期

相关硕士学位论文 前1条

1 戴昕;高效子图匹配算法研究[D];北京交通大学;2016年

本文编号：2828282