【摘要】：科技不斷發(fā)展,各門(mén)學(xué)科與計(jì)算機(jī)領(lǐng)域的結(jié)合越來(lái)越緊密,圖作為重要的數(shù)據(jù)結(jié)構(gòu),其應(yīng)用范圍不斷拓廣。蛋白質(zhì)網(wǎng)絡(luò),社交網(wǎng)絡(luò)以及電子商務(wù)網(wǎng)絡(luò)等,都是以圖進(jìn)行建模的數(shù)據(jù)。隨著互聯(lián)網(wǎng)用戶成倍的增加以及各門(mén)學(xué)科問(wèn)題研究的深入,圖數(shù)據(jù)規(guī)模逐漸增大,形成了復(fù)雜而又密集的大規(guī)模圖結(jié)構(gòu),對(duì)海量圖數(shù)據(jù)進(jìn)行有效地管理和挖掘成為圖數(shù)據(jù)研究的關(guān)鍵。近年來(lái),在大規(guī)模圖上進(jìn)行子圖查詢的應(yīng)用倍受關(guān)注,傳統(tǒng)的子圖查詢方法適用于較小規(guī)模圖的查詢,如何優(yōu)化大規(guī)模圖結(jié)構(gòu)的存儲(chǔ)并高效的從海量圖數(shù)據(jù)中查找出特定結(jié)構(gòu)的子圖成為當(dāng)前研究的一項(xiàng)挑戰(zhàn)。因此,本文利用索引查詢的優(yōu)勢(shì),提出了一種在圖數(shù)據(jù)上建立特征索引的查詢方法,線下提取結(jié)點(diǎn)特征,建立索引結(jié)構(gòu),線上進(jìn)行索引遍歷�；谶@一索引,本文分別對(duì)星型結(jié)構(gòu)和非星型結(jié)構(gòu)兩種查詢模式進(jìn)行研究,在非星型結(jié)構(gòu)的子圖查詢中,定義了圖的模式分解概念,并對(duì)中間解構(gòu)建圖模型,經(jīng)過(guò)連接預(yù)處理后利用多連接方法計(jì)算最小代價(jià)確定連接順序,得到最小規(guī)模候選集和盡可能小的查詢結(jié)構(gòu),從而有效提高同構(gòu)檢測(cè)速度和查詢效率。本文的研究成果主要有:(1)提出鄰接點(diǎn)標(biāo)數(shù)特征表的定義,將數(shù)據(jù)圖結(jié)構(gòu)轉(zhuǎn)化為特征表的方式存儲(chǔ),結(jié)點(diǎn)的標(biāo)簽、度以及鄰接點(diǎn)不同標(biāo)簽及其個(gè)數(shù)四項(xiàng)信息作為特征對(duì)數(shù)據(jù)圖結(jié)點(diǎn)進(jìn)行分類,根據(jù)分類原則將結(jié)點(diǎn)及對(duì)應(yīng)的特征信息存儲(chǔ)在特征表中。線下提取特征存儲(chǔ)為特征表加快了索引的構(gòu)建。(2)提出利用特征表構(gòu)建鄰接點(diǎn)雙層索引Dulaq-Index的方法,根據(jù)特征表中結(jié)點(diǎn)的標(biāo)簽不同,每一類標(biāo)簽結(jié)點(diǎn)構(gòu)建一棵特征索引樹(shù)。根據(jù)特征表內(nèi)特征間的包含關(guān)系分別設(shè)計(jì)上層索引和下層索引,根據(jù)鄰接點(diǎn)標(biāo)簽個(gè)數(shù)是否唯一設(shè)計(jì)索引值,最終底層葉結(jié)點(diǎn)存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)圖結(jié)點(diǎn)信息。實(shí)驗(yàn)表明該方法顯著提高過(guò)濾效率,加速子圖查詢。(3)根據(jù)索引的特殊性,探究出星型結(jié)構(gòu)子圖的查詢方法。提取星型查詢圖星心特征,通過(guò)遍歷索引進(jìn)行過(guò)濾得到結(jié)果集,再依賴存儲(chǔ)結(jié)構(gòu)的特殊性,對(duì)結(jié)果集展開(kāi)得到最終查詢結(jié)果。該查詢算法極大提高了過(guò)濾能力并省略了對(duì)候選集的同構(gòu)判別過(guò)程,與目前廣泛應(yīng)用的提取特征路徑算法進(jìn)行比較,有效縮短了子圖查詢時(shí)間。(4)針對(duì)非星型結(jié)構(gòu)查詢圖的查詢,提出結(jié)構(gòu)的分解、子項(xiàng)過(guò)濾、中間解連接以及結(jié)果集同構(gòu)判斷的非星型圖查詢方法,定義了模式分解概念,提出基于圖模型的中間解連接預(yù)處理方法,并結(jié)合MVP多連接查詢算法,實(shí)現(xiàn)最小代價(jià)的中間解連接,得到的查詢結(jié)果集是較小規(guī)模的圖結(jié)構(gòu)。再對(duì)結(jié)果集進(jìn)行深度優(yōu)先遍歷得到最終的查詢結(jié)果。實(shí)驗(yàn)證明該方法大大縮小查詢圖候選集,有效提高了查詢效率。
【圖文】：

圖的規(guī)模也越來(lái)越大。在不同應(yīng)環(huán)境下結(jié)查詢是圖論中經(jīng)典的 NP 問(wèn)題，因此在解決，從而探尋更適合當(dāng)前情況的解決途徑。據(jù)圖和查詢圖：數(shù)據(jù)圖是無(wú)向的、有標(biāo)有如下：V 是結(jié)點(diǎn)集合；E 是無(wú)向邊集； 個(gè)結(jié)點(diǎn)的標(biāo)簽，其中 L (V) 。的、頂點(diǎn)標(biāo)記的圖，表示為 (,,,qqqqG VE (,,,)qqqq VE L對(duì)應(yīng)字母的含義相同。本文。 據(jù) 圖 G 的 結(jié) 點(diǎn) 集 V (G)={v1,v2,v3,v,v4),(v1,v5),v2,v6),(v2,v7),(v2,v8),(v3,v4),(v4,v5),(v9,v3),(v{A,B,C},L(v1)=L(v2)=L(v3)=L(v4)=L(v6)==C.

第 2 章 相關(guān)工作同構(gòu)：給定圖 (,,,)qqqqqG VE L和圖 G (V 有如下定義：對(duì)于任意結(jié)點(diǎn)qu V，，有 L(qqE，存在一條邊 fufuEij( (),()) 。其中 f 表示)表示 Gq 結(jié)點(diǎn)的標(biāo)簽，ijq(u ,u) E表示 Gq 結(jié) 是 Gq1 在 G 上的一個(gè)查詢結(jié)果， f : v1 v4)，并找到 Gq1 每個(gè)結(jié)點(diǎn)每條邊對(duì)應(yīng)到 G 的圖 G 上的映射 f 的結(jié)果 G1.
【學(xué)位授予單位】：遼寧大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：TP311.12

【參考文獻(xiàn)】

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

1 楊艷;紀(jì)安娜;金虎;;大規(guī)模數(shù)據(jù)圖上的個(gè)性化子圖匹配算法[J];計(jì)算機(jī)研究與發(fā)展;2015年S1期

2 于靜;劉燕兵;張宇;劉夢(mèng)雅;譚建龍;郭莉;;大規(guī)模圖數(shù)據(jù)匹配技術(shù)綜述[J];計(jì)算機(jī)研究與發(fā)展;2015年02期

3 王楠;王斌;李曉華;楊曉春;;支持動(dòng)態(tài)圖數(shù)據(jù)的子圖查詢方法[J];計(jì)算機(jī)科學(xué)與探索;2014年02期

4 孟凡榮;張青;閆秋艷;;基于信息熵的子圖匹配算法[J];計(jì)算機(jī)應(yīng)用研究;2012年11期

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

6 陳恕勝;劉衛(wèi)東;;基于圖的適應(yīng)性多連接查詢優(yōu)化算法[J];計(jì)算機(jī)工程;2009年10期

7 郭聰莉;朱莉;李向;;基于蟻群算法的多連接查詢優(yōu)化方法[J];計(jì)算機(jī)工程;2009年10期

8 王果,徐仁佐;結(jié)合哈希過(guò)濾的一種改進(jìn)多連接查詢優(yōu)化算法[J];計(jì)算機(jī)工程;2004年07期

9 陳玉華;組合星圖(Com-Star Graph)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的分解[J];云南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);1998年01期

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

1 郭騰;基于Spark的子圖匹配算法研究與實(shí)現(xiàn)[D];北京交通大學(xué);2017年

2 呂雪棟;大規(guī)模RDF圖數(shù)據(jù)的子圖匹配查詢研究[D];天津大學(xué);2016年

本文編號(hào)：2609297