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

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