大規(guī)模圖數(shù)據(jù)查詢處理關(guān)鍵技術(shù)研究

大規(guī)模圖數(shù)據(jù)查詢處理關(guān)鍵技術(shù)研究隨著互聯(lián)網(wǎng)和數(shù)據(jù)庫技術(shù)的不斷發(fā)展,作為一種通用的數(shù)據(jù)結(jié)構(gòu),圖數(shù)據(jù)已在越來越多的應(yīng)用中廣泛存在,例如生物信息網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、知識圖譜等。圖數(shù)據(jù)上的查詢處理(如最短路徑查詢、可達查詢、關(guān)鍵字查詢等)是數(shù)據(jù)庫領(lǐng)域最基礎(chǔ)的問題之一。尤其隨著現(xiàn)如今大數(shù)據(jù)時代的到來,如何在大規(guī)模圖數(shù)據(jù)上進行高效的查詢處理顯得日益重要。雖然研究者近年來在圖數(shù)據(jù)的查詢處理技術(shù)上已經(jīng)取得了長足的進展,但隨著數(shù)據(jù)發(fā)展日趨多樣性,在實際應(yīng)用中,圖數(shù)據(jù)混合了多種復(fù)雜的信息,如不確定信息、時空信息等。因此,為迎合用戶在實際生活中的需求,圖數(shù)據(jù)上的查詢處理需要針對特定環(huán)境下進行更加合理高效建模,并設(shè)計相應(yīng)的高效計算處理技巧。而另一方面,由于圖數(shù)據(jù)本身所具有的復(fù)雜拓撲結(jié)構(gòu)的性質(zhì),圖上的查詢處理大多計算復(fù)雜度非常高,因而為大數(shù)據(jù)環(huán)境下的高效計算帶來了巨大的挑戰(zhàn)。為此,本文從用戶在不同實際應(yīng)用場景下的需求入手進行分析,進行合理的建模,并提出了有針對性的高效查詢處理算法。(1)大規(guī)模關(guān)聯(lián)不確定圖上的最短路徑查詢。分析了實際應(yīng)用中圖數(shù)據(jù)上的不確定信息彼此間存在的相關(guān)性,從而提出了一種基于馬爾可夫網(wǎng)絡(luò)的關(guān)聯(lián)不確定圖模型,以克服現(xiàn)有獨立不確定圖模型中的不足。由于在關(guān)聯(lián)不確定圖模型上計算最短路徑概率是一個#P-難問題,本文提出了一種過濾-驗證的方法來高效地求解該問題。在過濾步驟中,本文計算出最短路徑概率的一系列上界。同時,設(shè)計一種概率最短路徑索引,來管理這些上界,并輔助利用這些上界來過濾掉對查詢結(jié)果無用的結(jié)點和邊。由于構(gòu)建最優(yōu)索引依然是一個NP-難問題,本文提供一種O(logn)-近似的多項式時間算法來構(gòu)建索引。在過濾步驟之后,僅剩余一小部分子圖作為候選集。驗證步驟在該候選集上進行高效的采樣算法來計算出最終結(jié)果。(2)分布式環(huán)境下不確定圖上的可達查詢。分析了在實際應(yīng)用中,尤其是大數(shù)據(jù)環(huán)境下,不確定圖數(shù)據(jù)通常是分布式存儲的。而現(xiàn)在有的不確定圖上的可達查詢均為集中式算法,且由于該問題是#P-完全的,即使在集中式小圖環(huán)境下計算,其代價也非常高。本文發(fā)現(xiàn),雖然在全圖上計算可達概率是#P-完全的,但在一大部分子圖上的可達概率卻是多項式時間可計算的。因此,本文提出一種分布式圖簡化和分布式確認的策略來高效地計算結(jié)果。在分布式圖簡化的步驟中,將所有的可達概率在多項式時間內(nèi)可計算的子圖簡化成一條單邊。在分布式確認步驟中,將該問題轉(zhuǎn)化為高效的表連接問題,并利用近似算法來計算最終結(jié)果。(3)大規(guī)模容錯知識圖譜上的關(guān)鍵字查詢。分析了容錯性是知識圖譜在現(xiàn)實生活中的主要特征之一。而現(xiàn)有的圖數(shù)據(jù)上關(guān)鍵字查詢定義如果直接應(yīng)用到容錯知識圖譜中則會返回給用戶錯誤的結(jié)果。為此,本文針對容錯知識圖譜環(huán)境設(shè)計了一種稱為置信r-團的關(guān)鍵字查詢定義,使其可以返回給用戶更合理的關(guān)鍵字查詢結(jié)果。另一方面,由于計算置信r-團中的r-團置信度是#P-難的,因此提出了一種過濾-驗證算法框架來高效地解決該問題。在過濾步驟中,計算出置信r-團的候選結(jié)構(gòu)和置信度上界,并設(shè)計出一種適應(yīng)于大數(shù)據(jù)環(huán)境的索引,將沒有機會出現(xiàn)在結(jié)果集中的結(jié)點和邊進行剪枝。大量的基于真實數(shù)據(jù)集的實驗證明,本文所提出的置信r-團定義所返回的結(jié)果比直接將傳統(tǒng)關(guān)鍵字查詢定義應(yīng)用到容錯知識圖譜中所返回的結(jié)果更能令用戶滿意,且所提出的算法具有高效性。(4)基于事件的社交網(wǎng)絡(luò)上事件參與規(guī)劃查詢。考慮在實際應(yīng)用中二分圖匹配結(jié)合了時空信息的情況,提出一種為基于事件的社交網(wǎng)絡(luò)平臺上的用戶制定個性化參與其感興趣的事件的規(guī)劃查詢問題。然而現(xiàn)有的技術(shù)要么忽略了參加每個事件的最少人數(shù)需求條件,要么假設(shè)所有的事件一旦發(fā)布,任何信息都不能被改變。這些假設(shè)在現(xiàn)實生活中均難以實現(xiàn)。為此,本文提出了一個復(fù)雜事件規(guī)劃(GEPC)問題及其動態(tài)變種(IEP)問題,并證明這兩個問題都是NP-難的。因而,提出了帶誤差界保障的近似算法來解決這些問題。大量基于真實數(shù)據(jù)集的