本文關(guān)鍵詞：異構(gòu)信息網(wǎng)查詢和分析研究

  更多相關(guān)文章： 異構(gòu)信息網(wǎng) 元路徑 可達性 聚集圖 立方體 冰山立方體

【摘要】：信息網(wǎng)絡(luò)表示現(xiàn)實世界中實體以及實體之間的聯(lián)系。隨著科技的進步和互聯(lián)網(wǎng)的普及,信息網(wǎng)絡(luò)應用廣泛,如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等。信息網(wǎng)絡(luò)可以用圖數(shù)據(jù)模型進行建模,包含頂點和邊兩個元素,其中頂點對應現(xiàn)實世界中的實體對象,邊對應實體之間的聯(lián)系。按照信息網(wǎng)絡(luò)中頂點和關(guān)系的類型的數(shù)量,信息網(wǎng)絡(luò)被劃分為兩類:同構(gòu)信息網(wǎng)和異構(gòu)信息網(wǎng)。同構(gòu)信息網(wǎng)中頂點和邊的類型都只有一種,如朋友網(wǎng)、作者合作網(wǎng)等。異構(gòu)信息網(wǎng)包含多種類型的頂點和邊。大多數(shù)真實世界的信息網(wǎng)絡(luò)都是異構(gòu)的,如知識圖譜、社交網(wǎng)絡(luò)、物聯(lián)網(wǎng)等。異構(gòu)信息網(wǎng)絡(luò)強大的表達能力使其蘊含大量有價值的信息,使異構(gòu)信息網(wǎng)絡(luò)查詢和分析研究具有重要的現(xiàn)實意義。本文運用算法學、數(shù)據(jù)分析和計算復雜性的相關(guān)技術(shù),結(jié)合異構(gòu)信息網(wǎng)信息豐富和結(jié)構(gòu)復雜的特點,對異構(gòu)信息網(wǎng)絡(luò)查詢和分析問題進行深入研究,主要研究成果概括如下:1.本文研究了異構(gòu)信息網(wǎng)上可達性查詢問題�？蛇_性查詢是查詢兩個頂點之間是否存在路徑連接,是信息網(wǎng)絡(luò)中的基本查詢。研究兩個頂點的關(guān)系時,首先考慮的查詢也是兩點的可達性。然而,信息網(wǎng)絡(luò)上的可達性查詢不涉及頂點的類型和邊的類型,且都是建立在有向無環(huán)圖的基礎(chǔ)上。在異構(gòu)信息網(wǎng)中環(huán)路是經(jīng)常存在的,把異構(gòu)信息網(wǎng)中強連通組件壓縮成一個頂點會丟失不同類型頂點之間的路徑信息,現(xiàn)有的信息網(wǎng)絡(luò)上可達性研究都無法解決異構(gòu)信息網(wǎng)上基于不同關(guān)系的可達性查詢。本文形式化的定義了異構(gòu)信息網(wǎng)上可達性查詢問題,并證明該問題的時間復雜性是PTIME的。隨著網(wǎng)絡(luò)規(guī)模的爆炸式增長,每個查詢都需要遍歷一遍網(wǎng)絡(luò)的時間開銷是不能容忍的。因此,本文提出MP索引結(jié)構(gòu)用于快速響應查詢。通過將網(wǎng)絡(luò)的元路徑按照長度進行分層,構(gòu)建元路徑的偏序圖。在偏序圖上選擇一部分元路徑,并預計算元路徑上頂點的可達信息,使多個查詢可以共享相同元路徑中頂點可達信息。在真實和人工數(shù)據(jù)集上實驗驗證了本文算法可以快速響應查詢。2.本文研究了異構(gòu)信息網(wǎng)上聚集算法。聚集操作允許用戶從特定的維度上觀察數(shù)據(jù)的視圖,是多維分析的基礎(chǔ)。然而,信息網(wǎng)絡(luò)上的聚集操作只基于同構(gòu)信息網(wǎng)上頂點的屬性維度,與頂點的類型、邊的類型、以及網(wǎng)絡(luò)的結(jié)構(gòu)無關(guān)。異構(gòu)信息網(wǎng)不僅包含多種類型的頂點,還包含多種類型的關(guān)系,聚集的維度不應該僅限于頂點的屬性,而忽略豐富的結(jié)構(gòu)信息。因此信息網(wǎng)絡(luò)上現(xiàn)有的聚集工作無法用于異構(gòu)信息網(wǎng)。本文提出了基于多種類型頂點和多種類型邊的聚集操作,聚集的維度包括:頂點的類型、頂點的屬性和邊的類型。定義了異構(gòu)信息網(wǎng)上基于圖熵的度量函數(shù),該函數(shù)能夠很好的刻畫異構(gòu)信息網(wǎng)中頂點在不同關(guān)系上的相似度。本文證明了異構(gòu)信息網(wǎng)上的聚集問題是NP難的,并提出了線性時間和空間的高效近似聚集算法。聚集算法包括兩個過程:信息維聚集和結(jié)構(gòu)維聚集。本文進一步證明了算法的近似比。最后在真實數(shù)據(jù)集上的實驗結(jié)果顯示異構(gòu)信息網(wǎng)上的聚集算法能夠在特定的維度上對異構(gòu)信息網(wǎng)進行深入的分析,并具有較好的可擴展性。3.本文研究了異構(gòu)信息網(wǎng)上立方體計算問題。立方體計算允許用戶從不同的維度觀察數(shù)據(jù)對象的概括,是多維數(shù)據(jù)分析的核心。由于信息網(wǎng)絡(luò)上聚集操作的維度定義的局限制,也導致其立方體物化技術(shù)只基于頂點的屬性維度,通過屬性子集合之間的包含關(guān)系,選擇部分立方體進行物化。異構(gòu)信息網(wǎng)上維度概念的復雜化,使得傳統(tǒng)立方體物化技術(shù)并不適用于異構(gòu)信息網(wǎng)。本文提出了異構(gòu)信息網(wǎng)上立方體概念,從多個維度分析網(wǎng)絡(luò):頂點屬性、頂點類型和元路徑。本文研究了異構(gòu)信息網(wǎng)上的部分立方體物化問題,證明了該問題是NP難的。為了解決部分立方體物化問題,本文提出了異構(gòu)信息網(wǎng)上聚集圖之間兩種依賴關(guān)系:屬性依賴和路徑依賴,利用這兩種依賴關(guān)系建立代價模型和構(gòu)建方體格。本文為解決部分立方體物化問題提出了貪心算法,證明了該算法的近似比。在真實數(shù)據(jù)集上的實驗結(jié)果顯示異構(gòu)信息網(wǎng)立方體可以從多個維度上對網(wǎng)絡(luò)進行有效的分析,部分立方體物化算法可以提高查詢效率。4.本文研究了異構(gòu)信息網(wǎng)上近似冰山立方體問題。冰山立方體問題是計算聚集值大于閾值的立方體,是多維數(shù)據(jù)分析中的重要操作。然而,現(xiàn)有信息網(wǎng)絡(luò)上冰山立方體也是基于同構(gòu)信息網(wǎng)中頂點的屬性維度。顯然,這并不適用于異構(gòu)信息網(wǎng)。對于具有多種類型頂點和邊的異構(gòu)信息網(wǎng)來說,冰山立方體需要涉及頂點的屬性維度、類型維度,以及結(jié)構(gòu)維度,聚集函數(shù)也更加復雜。因此,需要一種新的冰山立方體定義,刻畫異構(gòu)信息網(wǎng)復雜的語義和結(jié)構(gòu)。本文形式化的定義了異構(gòu)信息網(wǎng)上冰山立方體,證明了該問題是NP難的。為了快速求解問題,本文設(shè)計了基于隨機游走的近似算法,并證明了基于隨機游走計算頂點相似性的相對誤差界。本文設(shè)計了兩種剪枝策略。當聚集函數(shù)滿足單調(diào)性時,可以提前結(jié)束方體計算或直接對方體進行剪枝。在真實和人工數(shù)據(jù)集上進行了大量實驗,結(jié)果顯示冰山立方體可以幫助用戶發(fā)現(xiàn)感興趣的聚集結(jié)果,近似算法和剪枝策略算法大大縮短查詢時間。
【學位授予單位】：哈爾濱工業(yè)大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：TP391.3

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 魏震方;宋正德;;云計算環(huán)境下異構(gòu)信息的發(fā)現(xiàn)機制與管理方法研究[J];商場現(xiàn)代化;2011年23期

2 王樂,強曉遠,孫莉;基于本體模型異構(gòu)信息交互的研究[J];微型機與應用;2005年01期

3 董明哲,張同軍;基于信息語義的異構(gòu)信息集成方法[J];計算機工程;2005年02期

4 李艾丹;薛中玉;李春梅;;異構(gòu)信息知識挖掘與可視化分析系統(tǒng)架構(gòu)模型解析[J];中國科技論壇;2012年10期

5 李劍;宋靖宇;鐘華;;基于本體的異構(gòu)信息集成查詢劃分及轉(zhuǎn)換[J];軟件學報;2007年10期

6 李艾丹;薛中玉;李春梅;;異構(gòu)信息知識挖掘與可視化系統(tǒng)處理流程解析[J];圖書館學研究;2012年14期

7 康文杰;鄭倩冰;陳侃;;基于社會網(wǎng)絡(luò)分析的學術(shù)合作關(guān)系研究[J];計算機技術(shù)與發(fā)展;2014年05期

8 史達;楊洋;;一種面向多層次異構(gòu)信息平臺的數(shù)據(jù)訪問鏈路識別算法[J];信息與控制;2014年01期

9 劉鈺峰;李仁發(fā);;基于查詢—文檔異構(gòu)信息網(wǎng)絡(luò)的半監(jiān)督學習[J];通信學報;2014年08期

10 徐壽芳;嵇美華;曾益坤;;基于本體的異構(gòu)電子商務信息集成探析[J];紹興文理學院學報(自然科學版);2008年01期

中國重要報紙全文數(shù)據(jù)庫 前2條

1 陳友梅;DB2信息集成提速異構(gòu)信息管理[N];中國計算機報;2003年

2 齊向真;我市兩項目獲科技部863計劃批復[N];太原日報;2012年

中國博士學位論文全文數(shù)據(jù)庫 前5條

1 黃冬;面向網(wǎng)絡(luò)金融知識服務的模型與方法研究[D];哈爾濱工業(yè)大學;2015年

2 尹丹;異構(gòu)信息網(wǎng)查詢和分析研究[D];哈爾濱工業(yè)大學;2016年

3 劉鈺峰;異構(gòu)信息網(wǎng)絡(luò)檢索技術(shù)研究[D];湖南大學;2014年

4 李朋;異構(gòu)信息網(wǎng)絡(luò)分析模型及其應用研究[D];重慶大學;2013年

5 王小剛;異構(gòu)信息集成環(huán)境中基于語義的查詢研究[D];華中科技大學;2006年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 朱敏;極性異構(gòu)信息網(wǎng)絡(luò)相關(guān)性搜索技術(shù)研究[D];山東大學;2015年

2 童浩;異構(gòu)信息網(wǎng)絡(luò)進化協(xié)同聚類算法的研究[D];福州大學;2014年

3 羅琛;異構(gòu)信息網(wǎng)絡(luò)上半監(jiān)督機器學習算法研究[D];吉林大學;2015年

4 王倩;異構(gòu)信息網(wǎng)絡(luò)上的主題建模研究[D];山東大學;2014年

5 吳晶;面向異構(gòu)信息集成的數(shù)據(jù)服務通道的設(shè)計與實現(xiàn)[D];電子科技大學;2013年

6 李立;基于元路徑選擇和融合的異構(gòu)信息網(wǎng)絡(luò)社區(qū)挖掘算法研究[D];西安電子科技大學;2014年

7 肖穎;面向信息集成的異構(gòu)信息描述方法研究[D];國防科學技術(shù)大學;2003年

8 賈偉;云環(huán)境下異構(gòu)信息交換模板的研究與設(shè)計[D];北京郵電大學;2012年

9 潘麗;極性異構(gòu)信息網(wǎng)絡(luò)的聯(lián)系預測技術(shù)研究[D];山東大學;2014年

10 豆榮剛;基于異構(gòu)信息的債券知識服務的研究與實現(xiàn)[D];哈爾濱工業(yè)大學;2013年

，

本文編號：1276471