大規(guī)模圖數(shù)據(jù)可達(dá)性索引技術(shù)的應(yīng)用

馮浩然 長沙市實(shí)驗(yàn)中學(xué)

大規(guī)模圖數(shù)據(jù)可達(dá)性索引技術(shù)的應(yīng)用

馮浩然 長沙市實(shí)驗(yàn)中學(xué)

我們進(jìn)入大數(shù)據(jù)時(shí)代后，數(shù)據(jù)的數(shù)量與規(guī)模明顯增加，而很多數(shù)據(jù)的結(jié)構(gòu)較為復(fù)雜，需用數(shù)據(jù)模型展示，由此，大規(guī)模圖數(shù)據(jù)可達(dá)性索引技術(shù)開始大范圍應(yīng)用，讓數(shù)據(jù)索引更加精準(zhǔn)，展示數(shù)據(jù)，提高了索引的效率。本文先論述了技術(shù)的應(yīng)用，隨后闡述了可達(dá)性索引的研究現(xiàn)狀。

可達(dá)性索引 生物信息網(wǎng) 社交網(wǎng)絡(luò)

當(dāng)下，大數(shù)據(jù)已經(jīng)成為我們經(jīng)常提及的詞匯，其具有的特點(diǎn)是，數(shù)據(jù)種類具有多樣性、結(jié)構(gòu)更加復(fù)雜，針對這一情況，我們可以采用大規(guī)模圖數(shù)據(jù)可達(dá)性索引技術(shù)，完成數(shù)據(jù)的收集，并用較短的時(shí)間匹配數(shù)據(jù)。但該技術(shù)仍有很多問題需要完善。

1 大規(guī)模圖數(shù)據(jù)可達(dá)性索引技術(shù)的應(yīng)用

現(xiàn)在，可達(dá)性索引已經(jīng)在多個(gè)計(jì)算機(jī)領(lǐng)域廣泛應(yīng)用，包括軟件工程、編程語言等，而它的應(yīng)用，也可以強(qiáng)化其他應(yīng)用算法的效果。比如Kijkstra等。

1.1 語義網(wǎng)

建立語義網(wǎng)的目標(biāo)是，機(jī)器可以理解在Web上發(fā)布的信息，轉(zhuǎn)化數(shù)據(jù)存儲(chǔ)的形式，讓其從原有的數(shù)據(jù)轉(zhuǎn)化為RDF、XML，其中XML是用文檔的方式存在，整體結(jié)構(gòu)為樹狀，如果所有數(shù)據(jù)中存在ID/IDF關(guān)系，需用圖表示，而RDF具有的關(guān)系為三元關(guān)系，也需要用圖表示。同時(shí)，RDF、XML也有各自的查詢語言，這兩種查詢語言都需要分析相應(yīng)的路徑，可達(dá)性查詢在其中起到的作用是，找到合適的路徑并進(jìn)行匹配。

1.2 本體

本體的定義是概念的集合，具有概念屬性，在同一個(gè)范疇內(nèi)不同的概念有相互關(guān)系，本體會(huì)根據(jù)關(guān)系的范圍，在特定的范疇內(nèi)完成推理。本體推理出來的內(nèi)容可在語義網(wǎng)中應(yīng)用。語義網(wǎng)內(nèi)，推理引擎會(huì)搜集所有推理后的結(jié)論，并把這些結(jié)論放到RDF數(shù)據(jù)中，加快推理的過程，比如，若是類C1為類C2的子類，C2又是C3的子類，由此推出，C1為C3的子類，簡化了原有的推理過程。

1.3 生物信息網(wǎng)

隨著數(shù)據(jù)獲取技術(shù)的發(fā)展，用高吞吐量獲取數(shù)據(jù)的方式已經(jīng)廣泛應(yīng)用，生物學(xué)家用這一方式可以搜集到大量的數(shù)據(jù)，而很多數(shù)據(jù)都需要用異構(gòu)圖顯示，比如代謝路徑分析、信號傳播網(wǎng)絡(luò)數(shù)據(jù)等。生物學(xué)家把這些數(shù)據(jù)集中到一起后，會(huì)用頂點(diǎn)或邊表示數(shù)據(jù)內(nèi)的結(jié)構(gòu)，即頂點(diǎn)可以代表蛋白質(zhì)、化合物等，而邊會(huì)連接不同的頂點(diǎn)，用于表示兩個(gè)頂點(diǎn)之間的關(guān)系。比如基因控制網(wǎng)絡(luò)數(shù)據(jù)，提出用基因A是否可以控制基因B，是直接控制還是間接控制，這恰巧對應(yīng)可達(dá)性查詢的內(nèi)容。

1.4 社交網(wǎng)絡(luò)

任意一個(gè)社交網(wǎng)絡(luò)中，每個(gè)用戶都是一個(gè)頂點(diǎn)，如果這兩個(gè)用戶之間可以建立聯(lián)系，頂點(diǎn)間會(huì)用一邊連接，而用戶之間的關(guān)系存在明顯的差異，包括父子、兄妹、姐妹等，需在邊的上方標(biāo)記兩個(gè)用戶之間的關(guān)系。同時(shí)，在整個(gè)社交網(wǎng)絡(luò)中，大部分查詢都需要先判斷兩個(gè)節(jié)點(diǎn)是否真正存在關(guān)系，而這一查詢方式即為可達(dá)性查詢。比如，我們想知道用戶A與B是否是遠(yuǎn)親關(guān)系，需探查兩點(diǎn)連接的路徑，分析周圍不同邊代表的關(guān)系，由此判斷A和B之間的關(guān)系。

此外，其在社交網(wǎng)絡(luò)的查詢中，會(huì)運(yùn)用子圖查詢，即子圖查詢是選擇一個(gè)圖數(shù)據(jù)庫與一個(gè)需要查詢的查詢圖，待查詢后把所有結(jié)果輸出，但因?yàn)椴樵儓D的結(jié)構(gòu)是隨機(jī)的，所以在查詢的過程中，要在所有數(shù)據(jù)庫中找到同構(gòu)圖，完成子圖匹配。其使用的算法是統(tǒng)計(jì)啟發(fā)式算法，具體的操作方式是，運(yùn)用信息熵，發(fā)揮信息上的度量作用，并讓其作為兩個(gè)圖是否匹配的依據(jù)，避免兩個(gè)相鄰的點(diǎn)過度匹配，提高查詢效率。其體現(xiàn)的思想是：在查詢中加入信息熵，并建立一個(gè)動(dòng)態(tài)模型與評價(jià)標(biāo)準(zhǔn)，隨后，根據(jù)動(dòng)態(tài)模型提出匹配的算法，最終對比不同的實(shí)驗(yàn)結(jié)果，分析結(jié)果的有效性。

1.5 復(fù)雜查詢處理

對于復(fù)雜查詢處理，可以通過可達(dá)性索引加快匹配算法的操作，通過最短的路徑查詢到相關(guān)信息，并完成子圖的匹配工作。

2 可達(dá)性索引的研究現(xiàn)狀

基于上述五方面可達(dá)性索引的應(yīng)用，可以總結(jié)出以下內(nèi)容：

從可達(dá)性索引發(fā)展至今，為擴(kuò)大其應(yīng)用范圍，很多索引方法被推出，而所有方法的選擇，都是為了讓時(shí)間、規(guī)模及模型構(gòu)建達(dá)到平衡，并可以分成不同的類型。從數(shù)據(jù)規(guī)模的角度來看，可以分為三類，包括小型、中型、大型數(shù)據(jù)規(guī)模，每個(gè)規(guī)模的數(shù)據(jù)都有不同的等級，依次為萬級以下、百萬以下、百萬以上，可以使用的查詢方式是有無約束查詢、動(dòng)態(tài)與靜態(tài)查詢。而以最大圖數(shù)據(jù)規(guī)模作為劃分標(biāo)準(zhǔn)，可以把索引方式分三種，分別是小規(guī)模、中規(guī)模、大規(guī)模的索引，若是把圖數(shù)據(jù)類型作為分類標(biāo)準(zhǔn)，可以使用靜態(tài)與動(dòng)態(tài)兩種索引方式。其中，所有查詢與索引的方式中，靜態(tài)與動(dòng)態(tài)是較為常用的方式，前者可以用于大型、中型、小型數(shù)據(jù)圖非限制的索引，以及中小型數(shù)據(jù)土受限的索引，后者因?yàn)閿?shù)據(jù)結(jié)構(gòu)較為復(fù)雜，不易動(dòng)態(tài)維護(hù)，所以運(yùn)用較少，其分類與靜態(tài)索引相同，但不可以用于中小型數(shù)據(jù)類型受限的索引。

3 結(jié)語

綜上所述，大規(guī)模圖數(shù)據(jù)可達(dá)性索引技術(shù)可以在多方面應(yīng)用，包括語義網(wǎng)、本體、生物信息網(wǎng)、社交網(wǎng)絡(luò)、復(fù)雜查詢處理等，有著良好的應(yīng)用前景。

[1]張瑞浩.大規(guī)模圖的可達(dá)性查詢算法研究[J].信息與電腦(理論版),2015,(17)

[2]孔揚(yáng)鑫,金澈清,王曉玲.基于手機(jī)軌跡數(shù)據(jù)的人口流動(dòng)分析[J].計(jì)算機(jī)應(yīng)用,2016,36(01)