【摘要】：有向標(biāo)簽圖作為重要的數(shù)據(jù)表示模型,廣泛應(yīng)用于社交網(wǎng)絡(luò)、語義網(wǎng)分析等信息技術(shù)相關(guān)的研究領(lǐng)域,子圖匹配查詢是圖數(shù)據(jù)管理的重要研究問題,引起了研究者的廣泛關(guān)注.有向標(biāo)簽圖的子圖同構(gòu)和子圖模擬匹配查詢由于代價(jià)極高,不適用于大規(guī)模圖數(shù)據(jù)的查詢處理.本文針對有向標(biāo)簽圖,研究基于自適應(yīng)結(jié)構(gòu)概要的子圖匹配查詢算法.首先基于圖壓縮的思想,提出一種滿足頂點(diǎn)"局部雙擬"關(guān)系且具有自適應(yīng)更新特性的有向標(biāo)簽圖結(jié)構(gòu)概要模型,在縮小數(shù)據(jù)圖規(guī)模的基礎(chǔ)上,適應(yīng)查詢圖的結(jié)構(gòu);然后采用圖模擬方式,提出基于自適應(yīng)結(jié)構(gòu)概要模型的子圖匹配查詢算法,根據(jù)查詢圖頂點(diǎn)的標(biāo)簽,對與其匹配的結(jié)構(gòu)概要頂點(diǎn)按照其中包含數(shù)據(jù)圖頂點(diǎn)的數(shù)量由小到大排序,根據(jù)查詢圖頂點(diǎn)之間的rank差值在結(jié)構(gòu)概要模型中實(shí)現(xiàn)頂點(diǎn)匹配;最后在真實(shí)數(shù)據(jù)集和模擬數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),結(jié)果表明:(1)自適應(yīng)結(jié)構(gòu)概要模型可根據(jù)查詢圖結(jié)構(gòu),實(shí)現(xiàn)對數(shù)據(jù)圖的最大壓縮;(2)可在O(|E|log|V|)的總體時(shí)間復(fù)雜度內(nèi)實(shí)現(xiàn)結(jié)構(gòu)概要的自適應(yīng)更新以及基于圖模擬方式的子圖匹配查詢.
[Abstract]:As an important data representation model, directed label graph is widely used in the research fields of information technology, such as social network, semantic web analysis and so on. Subgraph matching query is an important research problem in graph data management, which has attracted extensive attention of researchers. The subgraph isomorphism of directed label graph and the subgraph simulated matching query are not suitable for the query processing of large-scale graph data due to the high cost. In this paper, a subgraph matching query algorithm based on adaptive structure summary is studied for directed label graph. Firstly, based on the idea of graph compression, a structure summary model of directed label graph is proposed, which satisfies the vertex "local double fitting" relation and has the characteristic of adaptive updating. On the basis of reducing the scale of data graph, it adapts to the structure of query graph. Then a subgraph matching query algorithm based on adaptive structure summary model is proposed by using graph simulation. According to the label of query graph vertices, the matching structure summary vertices are sorted according to the number of vertices containing data graph from small to large. According to the rank difference between the vertices of the query graph, the vertex matching is realized in the structure summary model. Finally, the experiments are carried out on the real data set and the simulated data set. The results show that: (1) the adaptive structure summary model can be based on the structure of the query graph. The maximum compression of the data graph is realized. (2) the adaptive updating of the structure outline and the query of subgraph matching based on graph simulation can be realized within the total time complexity of O (E?
【作者單位】： 南開大學(xué)計(jì)算機(jī)與控制工程學(xué)院;南開大學(xué)軟件學(xué)院;
【基金】：國家“八六三”高技術(shù)研究發(fā)展計(jì)劃項(xiàng)目基金(2013AA013204,2015AA015401) 國家自然科學(xué)基金(61170184,61402243) 天津市自然科學(xué)基金(13ZCZDGX02200,13ZCZDGX01098,13JCQNJC00100,16JCTPJC53700)資助~~
【分類號】：O157.5

【相似文獻(xiàn)】

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

1 聶志峰,王昌田,聶峻峰;自適應(yīng)結(jié)構(gòu)補(bǔ)償器的研究[J];山東科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2003年01期

2 隋允康,邵建義;自適應(yīng)結(jié)構(gòu)多工況下強(qiáng)度控制的研究[J];力學(xué)學(xué)報(bào);2002年02期

3 張連文,夏人偉,曾廣武;自適應(yīng)結(jié)構(gòu)頻率和阻尼比的計(jì)算[J];應(yīng)用數(shù)學(xué)和力學(xué);1999年06期

4 龐勤;;2010年的AIAA力學(xué)國際會議[J];強(qiáng)度與環(huán)境;2009年03期

5 羅曉平;黃海;;自適應(yīng)桁架結(jié)構(gòu)振動(dòng)控制及其PCL仿真[J];機(jī)械科學(xué)與技術(shù);2007年01期

6 于明;二維自適應(yīng)結(jié)構(gòu)網(wǎng)格的變分生成方法[J];計(jì)算物理;2004年01期

7 朱德懋,張方,陳國平;自適應(yīng)結(jié)構(gòu)減振技術(shù)[J];應(yīng)用力學(xué)學(xué)報(bào);2001年S1期

8 隋允康,邵建義;自適應(yīng)超靜定桁架結(jié)構(gòu)強(qiáng)度控制的研究[J];固體力學(xué)學(xué)報(bào);2001年02期

9 陳勇,陶寶祺,高，

本文編號：2231033