馮浩然 長沙市實驗中學

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

馮浩然 長沙市實驗中學

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

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

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

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

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

1.1 語義網(wǎng)

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

1.2 本體

本體的定義是概念的集合，具有概念屬性，在同一個范疇內(nèi)不同的概念有相互關(guān)系，本體會根據(jù)關(guān)系的范圍，在特定的范疇內(nèi)完成推理。本體推理出來的內(nèi)容可在語義網(wǎng)中應(yīng)用。語義網(wǎng)內(nèi)，推理引擎會搜集所有推理后的結(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)用，生物學家用這一方式可以搜集到大量的數(shù)據(jù)，而很多數(shù)據(jù)都需要用異構(gòu)圖顯示，比如代謝路徑分析、信號傳播網(wǎng)絡(luò)數(shù)據(jù)等。生物學家把這些數(shù)據(jù)集中到一起后，會用頂點或邊表示數(shù)據(jù)內(nèi)的結(jié)構(gòu)，即頂點可以代表蛋白質(zhì)、化合物等，而邊會連接不同的頂點，用于表示兩個頂點之間的關(guān)系。比如基因控制網(wǎng)絡(luò)數(shù)據(jù)，提出用基因A是否可以控制基因B，是直接控制還是間接控制，這恰巧對應(yīng)可達性查詢的內(nèi)容。

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

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

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

1.5 復(fù)雜查詢處理

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

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

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

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

3 結(jié)語

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

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

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