基于自適應(yīng)結(jié)構(gòu)概要的有向標(biāo)前圖子圖查詢匹配算法研究.pdf

1、有向標(biāo)簽圖作為重要的數(shù)據(jù)表示模型，廣泛應(yīng)用于社交網(wǎng)絡(luò)、生物信息學(xué)、語(yǔ)義 web等信息技術(shù)相關(guān)的研究領(lǐng)域。目前，隨著上述領(lǐng)域數(shù)據(jù)規(guī)模的快速增長(zhǎng)，如何高效管理較大規(guī)模的有向標(biāo)簽圖數(shù)據(jù)，成為了數(shù)據(jù)管理領(lǐng)域的熱點(diǎn)研究問題，其中，子圖查詢匹配問題，由于其應(yīng)用的廣泛性而備受關(guān)注。如何高效地在較大規(guī)模有向標(biāo)簽圖數(shù)據(jù)上進(jìn)行子圖的查詢匹配，成為本文的主要研究目標(biāo)。
　　本文分析并總結(jié)了有向標(biāo)簽圖子圖模糊查詢匹配技術(shù)在國(guó)內(nèi)外的研究現(xiàn)狀，并在此基礎(chǔ)上，

2、以圖壓縮的思想作為基礎(chǔ)，對(duì)較大規(guī)模有向標(biāo)簽圖上的子圖查詢匹配技術(shù)進(jìn)行深入研究，主要工作包括：
　　首先，提出了一種能夠隨查詢圖動(dòng)態(tài)自適應(yīng)更新的有向標(biāo)簽圖結(jié)構(gòu)概要模型——自適應(yīng)結(jié)構(gòu)概要ASSG(AdaptiveStructuralSummary ofGraphdata)。本文基于圖壓縮的思想構(gòu)建有向標(biāo)簽圖的自適應(yīng)結(jié)構(gòu)概要。該結(jié)構(gòu)概要可隨著查詢圖的引入而進(jìn)行自適應(yīng)更新，以應(yīng)對(duì)不同查詢圖的查詢匹配。另外，結(jié)構(gòu)概要模型對(duì)于有向標(biāo)簽圖中從未

3、涉及查詢的部分保持高度壓縮，極大降低了存儲(chǔ)空間。
　　其次，基于自適應(yīng)結(jié)構(gòu)概要，提出較大規(guī)模有向標(biāo)簽圖上的子圖查詢匹配算法。本文通過結(jié)構(gòu)概要模型定位候選匹配頂點(diǎn)集，并在引入查詢圖時(shí)更新結(jié)構(gòu)概要模型的結(jié)構(gòu)，最后通過子圖查詢匹配算法，可在接近線性的時(shí)間復(fù)雜度內(nèi)，實(shí)現(xiàn)對(duì)查詢圖的查詢匹配。
　　最后，本文在真實(shí)數(shù)據(jù)集 California、Citation、Internet及半模擬數(shù)據(jù)集Synthetic上進(jìn)行了大量的對(duì)比實(shí)驗(yàn)，對(duì)主