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