隨著計算機(jī)存儲器技術(shù)的發(fā)展,近年來出現(xiàn)了一類新型存儲器—按字節(jié)尋址非易失存儲器(byte-addressable non-volatile memory),簡稱NVM。NVM融合了傳統(tǒng)DRAM按字節(jié)尋址和傳統(tǒng)外存非易失的特點(diǎn),有望在將來成為計算機(jī)存儲結(jié)構(gòu)層次的重要組成部分。然而,由于NVM的讀寫不對稱性,現(xiàn)有的內(nèi)存算法可能不再適用�；谶@一背景,本文著重研究了在NVM上的高效子圖匹配算法問題。本文的主要研究內(nèi)容分為以下幾個方面:首先研究了基于NVM的高效精確子圖匹配算法。由于對NVM進(jìn)行一次寫的代價顯著高于其讀代價,因此算法的關(guān)鍵在于用以一定的讀操作為代價來盡量減少寫操作的次數(shù),從而提高算法的運(yùn)行效率。本文通過對現(xiàn)有算法的定性和定量分析,找到了現(xiàn)有算法涉及較多寫次數(shù)的關(guān)鍵部分,并提出了一種新的數(shù)據(jù)結(jié)構(gòu)ILD表以減少匹配過程中的寫操作次數(shù),解決了傳統(tǒng)回溯算法的寫操作數(shù)量過多的問題,從而提高算法在NVM上的性能。其次在上述算法的基礎(chǔ)之上研究在NVM上基于動態(tài)圖更新的高效子圖匹配算法。本文改進(jìn)了IDL表的存儲結(jié)構(gòu),使得在圖更新時帶來的寫操作次數(shù)盡可能少,更新代價盡可能小;另一方面本文提出了一種對更新結(jié)果出現(xiàn)區(qū)域的限制策略,減少更新算法的搜索空間大小,從而提高算法的運(yùn)行效率。然后基于傳統(tǒng)的近似子圖匹配算法研究在NVM上高效的近似算法,研究能否以較少的精確性損失為代價進(jìn)一步提高算法的效率。本文提出了基于雙向模擬的子圖匹配問題的定義,解決了傳統(tǒng)基于模擬的定義帶來的頂點(diǎn)錯配問題,并基于這一定義,通過限制現(xiàn)有算法對輔助索引的建立,提出了兩個在NVM上的高效算法。最后對于本文提出的算法進(jìn)行了具體的實(shí)現(xiàn),并通過基于仿真平臺的實(shí)驗(yàn),比較了本文提出的各類算法和傳統(tǒng)算法在NVM上的運(yùn)行效率。實(shí)驗(yàn)結(jié)果表明本文提出的算法相對現(xiàn)有算法在運(yùn)行效率上有顯著的提升。
【學(xué)位單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2017
【中圖分類】：TP391.41;TP333
【部分圖文】：

圖 2-2 基本回溯算法舉例例給出一個基于回溯算法框架進(jìn)行子圖匹配嘗試圖，圖 2-1(b)為數(shù)據(jù)圖。假設(shè)匹配順序?yàn)?1, ， 的候選頂點(diǎn)集為 , 。一開始 被匹配

算法在DRAM和NVM上性能對比

圖 3-2 通過 ILD 表獲取候選頂點(diǎn)集圖 3-2(b)是一個數(shù)據(jù)圖，圖 3-2(a)是其對應(yīng)的 ILD 表。圖 3-2(c)是待假設(shè)現(xiàn)在需要獲取查詢圖頂點(diǎn) 1的候選頂點(diǎn)集。 1的標(biāo)簽為 A，在

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 余靖;韓玉;;URSI:高效的子圖同構(gòu)查詢算法[J];燕山大學(xué)學(xué)報;2016年06期

2 張海威;解曉芳;段媛媛;溫延龍;張瑩;袁曉潔;;一種基于自適應(yīng)結(jié)構(gòu)概要的有向標(biāo)簽圖子圖匹配查詢算法[J];計算機(jī)學(xué)報;2017年01期

3 蔡濤;張永春;牛德姣;倪曉蓉;梁東鶯;;面向新型非易失存儲器的文件級磨損均衡機(jī)制[J];計算機(jī)研究與發(fā)展;2015年07期

4 陳東;王波;席耀一;唐浩浩;;基于鄰居向量的近似子圖匹配[J];計算機(jī)工程與設(shè)計;2014年11期

5 蔡濤;張永春;倪曉蓉;牛德姣;梁東鶯;周東明;;面向非易失存儲器外存系統(tǒng)的緩存機(jī)制[J];小型微型計算機(jī)系統(tǒng);2014年09期

6 黃云;洪佳明;覃遵躍;;大型網(wǎng)絡(luò)中近似子圖匹配研究[J];計算機(jī)工程;2012年18期

7 張一楠;鄒兆年;李建中;;不確定圖間α-β子圖同構(gòu)匹配算法[J];智能計算機(jī)與應(yīng)用;2011年05期

8 張一楠;高宏;張煒;;基于雙分支特征編碼的子圖查詢處理算法[J];計算機(jī)研究與發(fā)展;2011年S3期

9 張碩;李建中;高宏;鄒兆年;;一種多到一子圖同構(gòu)檢測方法[J];軟件學(xué)報;2010年03期

10 張志祥;李慶華;羅建明;;改進(jìn)的基于分解的子圖同構(gòu)算法[J];計算機(jī)科學(xué);2006年01期

相關(guān)碩士學(xué)位論文 前1條

1 戴昕;高效子圖匹配算法研究[D];北京交通大學(xué);2016年

本文編號：2828282