隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的豐富與擴(kuò)展,圖作為常用的數(shù)據(jù)結(jié)構(gòu)之一,現(xiàn)實(shí)世界的諸多領(lǐng)域均用圖來描述其復(fù)雜而龐大的邏輯關(guān)系,如社交網(wǎng)、生物信息網(wǎng)、智能交通網(wǎng)等新興領(lǐng)域的建模。同時在某些復(fù)雜網(wǎng)絡(luò)中存在多種類別的頂點(diǎn),常利用標(biāo)簽圖對此類復(fù)雜網(wǎng)絡(luò)進(jìn)行建模。如社交網(wǎng)中的微博,我們可以用頂點(diǎn)表示微博用戶,任意用戶之間的關(guān)注情況可通過有向邊來表示,此時標(biāo)簽可用來表示用戶的性別、所在地、關(guān)注領(lǐng)域等信息。子圖查詢作為圖數(shù)據(jù)分析的關(guān)鍵問題,引起了研究者的廣泛關(guān)注。動態(tài)標(biāo)簽圖子圖查詢,即返回結(jié)構(gòu)及標(biāo)簽值均同構(gòu)于查詢圖的若干子圖。然而子圖同構(gòu)查詢是一個NP完全問題,隨著數(shù)據(jù)圖的增長且頻繁更新,查詢時間會大大增加,通過創(chuàng)建高質(zhì)量的索引結(jié)構(gòu)以提高查詢效率已成為解決這一問題的關(guān)鍵。例如:微博新用戶的注冊、老用戶的注銷、用戶間新增或取消關(guān)注等行為都會導(dǎo)致標(biāo)簽圖的動態(tài)變化。微博應(yīng)用中新用戶注冊、用戶添加關(guān)注等行為都將抽象為標(biāo)簽圖頂點(diǎn)或邊的插入,微博中用戶賬號注銷,取消關(guān)注等行為都將抽象為標(biāo)簽圖中頂點(diǎn)或邊的刪除。對現(xiàn)有子圖查詢算法的研究發(fā)現(xiàn),隨著圖數(shù)據(jù)規(guī)模增大且頻繁更新,傳統(tǒng)子圖查詢算法普遍存在查詢效率低、存儲開銷大、忽略頂點(diǎn)標(biāo)簽... 

【文章來源】：遼寧大學(xué)遼寧省 211工程院校

【文章頁數(shù)】：63 頁

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

【部分圖文】：

索引創(chuàng)建時間

43圖（f）圖 5-3 查詢操作執(zhí)行時間 本章小結(jié)通過上述實(shí)驗(yàn)結(jié)果可知，本文提出的支持動態(tài)有向標(biāo)簽圖的子圖查詢方大規(guī)模動態(tài)有向標(biāo)簽圖的分布式子圖查詢方法是都是有效可行的，兩種引構(gòu)造簡單且索引體積較小，更新時間短，該查詢方法在頻繁更新的動上表現(xiàn)出良好的查詢性能，并且時間和空間代價都很小。

【參考文獻(xiàn)】：
期刊論文
[1]基于增量信息索引的子圖查詢算法[J]. 王超琿,黃一夫.  計(jì)算機(jī)應(yīng)用與軟件. 2016(10)
[2]一種面向動態(tài)連續(xù)查詢的查詢索引[J]. 鄧澤,劉汪洋,陳丹.  計(jì)算機(jī)應(yīng)用與軟件. 2015(12)
[3]一種基于自適應(yīng)結(jié)構(gòu)概要的有向標(biāo)簽圖子圖匹配查詢算法[J]. 張海威,解曉芳,段媛媛,溫延龍,張瑩,袁曉潔.  計(jì)算機(jī)學(xué)報. 2017(01)
[4]大規(guī)模數(shù)據(jù)圖上的個性化子圖匹配算法[J]. 楊艷,紀(jì)安娜,金虎.  計(jì)算機(jī)研究與發(fā)展. 2015(S1)
[5]支持動態(tài)圖數(shù)據(jù)的子圖查詢方法[J]. 王楠,王斌,李曉華,楊曉春.  計(jì)算機(jī)科學(xué)與探索. 2014(02)
[6]不確定數(shù)據(jù)頻繁項(xiàng)集挖掘方法綜述[J]. 汪金苗,張龍波,鄧齊志,王鳳英,王勇.  計(jì)算機(jī)工程與應(yīng)用. 2011(20)



本文編號：3566754