標簽圖是指節(jié)點具有標識能力的一種特殊的圖結(jié)構(gòu),已經(jīng)普遍應用于地理社交網(wǎng)絡、電子商務網(wǎng)絡以及生物信息網(wǎng)絡等領域的建模。隨著科學與計算機技術飛速發(fā)展,上述各領域抽象的標簽圖除具有傳統(tǒng)的圖數(shù)據(jù)特點外,又呈現(xiàn)了數(shù)據(jù)規(guī)模巨大、數(shù)據(jù)增長過快以及數(shù)據(jù)更新頻繁等特點。子圖查詢因?qū)D數(shù)據(jù)分析具有重要意義得到了研究者的廣泛研究。然而,隨著標簽圖規(guī)模日益增大,人們逐漸傾向于只關注眾多查詢結(jié)果中一些高匹配結(jié)果,希望借助查詢結(jié)果之間的關系以及數(shù)量等快速獲取期望結(jié)果。因而,為了滿足用戶的個性化查詢需求,更具針對性的Top-K興趣子圖查詢方法應運而生。研究者考慮到傳統(tǒng)的無優(yōu)化策略的子圖查詢算法在大規(guī)模圖中難以應用的弊端,研究借助數(shù)據(jù)庫的索引技術實現(xiàn)對圖中節(jié)點或邊進行索引,或借助圖壓縮技術縮減數(shù)據(jù)圖規(guī)模以加快查詢效率。然而,大多數(shù)新研究的子圖查詢算法忽略了現(xiàn)階段的大部分標簽圖的數(shù)據(jù)增長過快以及數(shù)據(jù)更新過于頻繁的特點。同時,在Top-K興趣子圖查詢中,多借助邊的權值定義實體間的某種限制關系,這導致現(xiàn)有的針對無權圖的子圖查詢算法難以直接應用。因而如何實現(xiàn)在大規(guī)模且動態(tài)變化的加權標簽圖上的Top-K興趣子圖查詢成為圖數(shù)據(jù)處... 

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

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

【學位級別】：碩士

【部分圖文】：

索引構(gòu)建時間及存儲開銷

各算法查詢時間對比

第 5 章 實驗與分析圖 5-3(a)展示了在真實數(shù)據(jù)集 Youtube 上，隨著查詢圖規(guī)模 Q 的增加各算法查詢時間的對比情況。因為 RAM 和 RWM 算法在利用路徑過濾后，需要再次對比每個匹配中各邊的權值，因此，隨著查詢圖規(guī)模的增大，RAM 與 RWM 算法查詢時間會顯著增加。相比而言，DISQtop-K 與 PSM 算法隨著查詢圖規(guī)模的增加，查詢時間的增加會比較平緩。又因為查詢圖規(guī)模越大，因壓縮而被過濾的節(jié)點與邊越多，因此 DISQtop-K 算法在查詢圖規(guī)模較大時，會更有利。圖 5-3(b)展示了在真實數(shù)據(jù)集 DBLP 上，隨著查詢圖規(guī)模和 K 值的增大，DISQtop-K 算法查詢時間的變化情況。由圖可知，隨著查詢圖規(guī)模的增加，DISQtop-K 算法的查詢時間有所增加，但增加相對平緩。當查詢圖 Q 固定時，K 值變化時，查詢圖的波動較小。圖 5-3 驗證了 DISQtop-K 算法有較好的可擴展性。

【參考文獻】：
期刊論文
[1]一種基于自適應結(jié)構(gòu)概要的有向標簽圖子圖匹配查詢算法[J]. 張海威,解曉芳,段媛媛,溫延龍,張瑩,袁曉潔.  計算機學報. 2017(01)
[2]大規(guī)模數(shù)據(jù)圖上的個性化子圖匹配算法[J]. 楊艷,紀安娜,金虎.  計算機研究與發(fā)展. 2015(S1)
[3]不確定圖數(shù)據(jù)庫中高效查詢處理[J]. 張碩,高宏,李建中,鄒兆年.  計算機學報. 2009(10)
[4]不確定性數(shù)據(jù)管理技術研究綜述[J]. 周傲英,金澈清,王國仁,李建中.  計算機學報. 2009(01)
[5]基于滑動窗口的數(shù)據(jù)流連續(xù)J-A查詢的處理方法[J]. 王偉平,李建中,張冬冬,郭龍江.  軟件學報. 2006(04)



本文編號：3444716