標(biāo)簽圖作為一種重要的數(shù)據(jù)表示模型,廣泛應(yīng)用于生物化學(xué)、社交網(wǎng)絡(luò)、知識(shí)圖譜等領(lǐng)域,子圖匹配作為圖數(shù)據(jù)管理的一個(gè)重要操作,引起了研究者的普遍關(guān)注。本文針對(duì)標(biāo)簽圖的子圖匹配問(wèn)題進(jìn)行研究,分別給出了無(wú)重復(fù)標(biāo)簽圖的子圖匹配算法k~2-MDD-SubM和有重復(fù)標(biāo)簽圖的子圖匹配算法LCCP_SubM。本文的主要工作如下:（1）針對(duì)無(wú)重復(fù)標(biāo)簽圖,引入k~2-MDD對(duì)其進(jìn)行高效緊湊的表示以減小查詢規(guī)模,同時(shí)結(jié)合符號(hào)計(jì)算的邏輯運(yùn)算,給出一種子圖匹配算法k~2-MDD-SubM,該算法將原始的子圖匹配問(wèn)題轉(zhuǎn)化為基于k~2-MDD的布爾函數(shù)邏輯運(yùn)算。以Graemlin和PPI數(shù)據(jù)集為例進(jìn)行實(shí)驗(yàn),對(duì)于Graemlin數(shù)據(jù)集,實(shí)驗(yàn)結(jié)果表明k~2-MDD-SubM所需存儲(chǔ)的結(jié)點(diǎn)數(shù)僅為RI算法的35.83%,當(dāng)模式圖大小一定時(shí),隨著模式圖密度的逐漸減小,算法的查詢時(shí)間逐漸減少,且當(dāng)模式圖與目標(biāo)圖相同時(shí),其查詢效率優(yōu)于RI算法。驗(yàn)證了k~2-MDD-SubM算法存儲(chǔ)和查詢性能的優(yōu)越性;對(duì)于PPI數(shù)據(jù)集,實(shí)驗(yàn)結(jié)果表明k~2-MDD-SubM所需存儲(chǔ)的結(jié)點(diǎn)數(shù)僅為RI算法的57.19%,同樣隨著模式圖密度... 

【文章頁(yè)數(shù)】：61 頁(yè)

【學(xué)位級(jí)別】：碩士

【文章目錄】：
摘要
Abstract
第一章 緒論
    §1.1研究背景及意義
    §1.2國(guó)內(nèi)外研究現(xiàn)狀
    §1.3研究?jī)?nèi)容
    §1.4本文章節(jié)安排
第二章 相關(guān)知識(shí)介紹
    §2.1子圖匹配相關(guān)知識(shí)
    §2.2子圖匹配算法
    §2.3基于MDD的圖數(shù)據(jù)表示方法k~2-MDD
        §2.3.1k~2-MDD定義與邏輯操作
        §2.3.2實(shí)驗(yàn)相關(guān)軟件包
    §2.4本章小結(jié)
第三章 k~2-MDD-SubM：一種無(wú)重復(fù)標(biāo)簽圖的子圖匹配算法
    §3.1引言
    §3.2k~2-MDD-SubM算法
        §3.2.1無(wú)重復(fù)標(biāo)簽圖的子圖匹配定義
        §3.2.2k~2-MDD的構(gòu)造
        §3.2.3k~2-MDD-SubM算法過(guò)程
        §3.2.4k~2-MDD-SubM的復(fù)雜度分析
    §3.3實(shí)驗(yàn)與分析
        §3.3.1數(shù)據(jù)集
        §3.3.2實(shí)驗(yàn)結(jié)果與分析
    §3.4本章小結(jié)
第四章 LCCP_SubM：一種有重復(fù)標(biāo)簽圖的子圖匹配算法
    §4.1引言
    §4.2變量排序
        §4.2.1變量排序特征
        §4.2.2變量排序策略
    §4.3LCCP_SubM算法過(guò)程
        §4.3.1LCCP_SubM中的變量排序
        §4.3.2約束過(guò)濾條件以及算法過(guò)程
        §4.3.3LCCP_SubM的復(fù)雜度分析
    §4.4實(shí)驗(yàn)與分析
        §4.4.1數(shù)據(jù)集
        §4.4.2實(shí)驗(yàn)結(jié)果與分析
    §4.5本章小結(jié)
第五章 結(jié)束語(yǔ)
    §5.1主要研究工作總結(jié)
    §5.2研究工作展望
參考文獻(xiàn)
符號(hào)對(duì)照表
致謝
攻讀碩士學(xué)位期間的主要研究成果


【參考文獻(xiàn)】：
期刊論文
[1]動(dòng)態(tài)圖模式匹配技術(shù)綜述[J]. 許嘉,張千楨,趙翔,呂品,李陶深.  軟件學(xué)報(bào). 2018(03)
[2]基于包含度的子圖匹配方法[J]. 李瑞遠(yuǎn),洪亮.  軟件學(xué)報(bào). 2018(06)
[3]ERSearch:一種高效的子圖查詢算法[J]. 黃云,洪佳明,覃遵躍,鐘鍵,李夢(mèng)婷,印鑒.  電子學(xué)報(bào). 2017(02)
[4]大規(guī)模圖數(shù)據(jù)的k~2-MDD表示方法與操作研究[J]. 董榮勝,張新凱,劉華東,古天龍.  計(jì)算機(jī)研究與發(fā)展. 2016(12)
[5]一種基于自適應(yīng)結(jié)構(gòu)概要的有向標(biāo)簽圖子圖匹配查詢算法[J]. 張海威,解曉芳,段媛媛,溫延龍,張瑩,袁曉潔.  計(jì)算機(jī)學(xué)報(bào). 2017(01)
[6]大規(guī)模圖數(shù)據(jù)匹配技術(shù)綜述[J]. 于靜,劉燕兵,張宇,劉夢(mèng)雅,譚建龍,郭莉.  計(jì)算機(jī)研究與發(fā)展. 2015(02)
[7]基于圖數(shù)據(jù)挖掘算法的犯罪規(guī)律研究及應(yīng)用[J]. 唐德權(quán),張悅,賀永恒,肖自紅.  計(jì)算機(jī)技術(shù)與發(fā)展. 2011(11)



本文編號(hào)：3716618