RDF 圖模型支持下的知識圖譜數(shù)據(jù)索引與壓縮存儲算法

魯富宇，冷泳林

（渤海大學(xué) 信息科學(xué)與技術(shù)學(xué)院，遼寧 錦州 121013）

0 引言

隨著領(lǐng)域知識圖譜的不斷完善、規(guī)模的不斷擴大，其數(shù)據(jù)管理問題愈加重要［1］. RDF作為人工智能領(lǐng)域存儲和管理知識圖譜的通用框架，采用三元組形式描述知識，大量知識構(gòu)成三元組庫. 三元組庫以實體、屬性和值為基本構(gòu)件，通過屬性和值描述知識之間的關(guān)系. 同時一條三元組也可以看做是實體指向?qū)傩灾档挠邢蜻叄@些有向邊連接到一起構(gòu)成有向圖，圖頂點表示實體和值，有向邊表示屬性. 知識圖譜中包含了豐富的語義知識，這些語義知識構(gòu)成領(lǐng)域知識圖譜［2］. 根據(jù)鏈接開放數(shù)據(jù)發(fā)布的信息顯示，很多領(lǐng)域知識圖譜的規(guī)模在10億條以上，如維基百科和地理信息知識圖譜的三元組達到30億條，蛋白質(zhì)知識圖譜超過130億條. 如此大規(guī)模的領(lǐng)域知識圖譜數(shù)據(jù)給數(shù)據(jù)高效存儲和檢索都提出巨大挑戰(zhàn)［3］.

基于關(guān)系的RDF數(shù)據(jù)存儲是一種常見的存儲方式，三元組表［4-5］、垂直分割［6］以及屬性表［7］都是采用替代的關(guān)系存儲方式存儲RDF三元組，來加速數(shù)據(jù)檢索，但這種基于元組的存儲方式忽略了數(shù)據(jù)間知識的聯(lián)系，并且在處理大規(guī)模數(shù)據(jù)時的空值、自連接等問題嚴(yán)重影響了數(shù)據(jù)的檢索效率. 一些存儲索引系統(tǒng)如RDF-3X［8］，Hexastore［9］和SPOVC［10］通過構(gòu)建三元組不同組合方式的索引存儲多個索引副本，并輔助相應(yīng)的查詢優(yōu)化技術(shù)，提高了查詢效率. 當(dāng)面臨大規(guī)模數(shù)據(jù)時，這些索引都是以空間來換取時間效率的. 另外，gStore［11］采用樹狀索引和鄰接表的方式對RDF數(shù)據(jù)進行索引，TripleBit［12］依據(jù)RDF謂語對元組進行索引并進行壓縮存儲. 這兩種索引在執(zhí)行查詢過程中過濾大量不相關(guān)數(shù)據(jù)，提高查詢效率. 但它們都是基于元組的檢索，需要利用查詢優(yōu)化技術(shù)降低查詢中間結(jié)果. 為降低查詢中間結(jié)果，RP-index（RDF Path in?dex）［13］和RG-index（RDF graph index）［14］兩種基于路徑和圖的過濾索引用來實現(xiàn)數(shù)據(jù)的有效過濾. 其中RP-index索引RDF圖中入邊路徑信息，RG-index將路徑索引擴展至圖結(jié)構(gòu)索引實現(xiàn)元組的有效過濾，這兩種索引的規(guī)模會隨著圖規(guī)模的不斷擴大而迅速增加. 基于以上分析，自連接、副本和壓縮方法是影響SPARQL查詢效率的主要因素.

本文通過分析RDF數(shù)據(jù)發(fā)現(xiàn)，鏈?zhǔn)浇Y(jié)構(gòu)做為一種常見數(shù)據(jù)結(jié)構(gòu)，有效的反映出知識之間的關(guān)聯(lián)，在數(shù)據(jù)檢索和知識推理中都具有非常重要的作用. 基于此，提出一種基于路徑的索引樹（Path tree，P-tree）及建立在該索引結(jié)構(gòu)上的三元組壓縮和檢索算法（Compressed and retrieval triples，CRK2-triples），來實現(xiàn)RDF數(shù)據(jù)模型下知識圖譜數(shù)據(jù)的快速檢索.

1 路徑索引樹（P-tree）構(gòu)建

RDF有向圖的每條邊鏈接知識主體（主語）和知識主體所對應(yīng)的屬性值（賓語），邊代表著主體的特征. 通過對SPARQL查詢圖特征進行分析得出星型、鏈?zhǔn)健h(huán)型、樹型是SPARQL查詢圖的基本結(jié)構(gòu). 其中鏈?zhǔn)浇Y(jié)構(gòu)是指主語又同時作為賓語的結(jié)構(gòu)，本文針對鏈?zhǔn)竭@種常見的結(jié)構(gòu)，構(gòu)建P-tree索引.

給定一個RDF有向圖G，如果G中存在一個頂點v滿足鏈接它的所有邊中只有出邊，沒有入邊，則稱頂點v為源點. 相反，如果v滿足只有入邊沒有出邊，稱之為匯點. 對于一個RDF有向圖，從源點出發(fā)，沿有向邊的方向進行深度優(yōu)先遍歷，直到遇到第一個匯點結(jié)束，所得到的路徑，稱之為一條由源點到匯點的完整路徑. 將一個RDF知識圖譜按從源點到匯點進行分解，會得到多條完整路徑. 文獻［15］已經(jīng)證明，RDF圖中的任意一個實體或?qū)傩约八鼈冎g的有向邊都至少屬于一條完整路徑，由此可以保證一個RDF有向圖可以由一個完整路徑集合表示.

對于一個給定的SPARQL查詢，同樣也以源點到匯點的完整路徑分解方式將其分解為完整查詢路徑集合，文獻［15］同樣給出了如果SPARQL查詢是RDF子圖，那么一定至少存在一條完整路徑，滿足查詢路徑是完整路徑的子路徑.

由于RDF圖中頂點及邊都是采用統(tǒng)一資源標(biāo)識符（URI）進行表示，直接的字符串匹配查詢在查詢效率上有一定影響，而基于二進制的位串利用邏輯運算所進行的匹配查詢效率要明顯優(yōu)于字符串的匹配.因此本文對完整路徑及查詢路徑利用布魯姆過濾器進行編碼，生成能夠快速配的二進制位串.

將RDF圖分解成一個全路徑集合，集合中每一條全路徑上的邊信息構(gòu)成一條概要路徑，對于每條概要路徑將路徑上每條邊的屬性信息通過k個Hash函數(shù)h1，h2，…，hk映射到長度為m的向量V中，生成一個布魯姆編碼. 則所有的n條完整路徑對應(yīng)生成n個布魯姆編碼V1，V2，…，Vk. 接下來通過計算這n個編碼之間的漢明距離，得到任意一對完整路徑之間的相似性，然后利用AP聚類，對生成的n條完整路徑進行聚類.

AP聚類在聚類時不需要指定聚類中心，將所有數(shù)據(jù)作為潛在的聚類中心，然后通過迭代的方式在數(shù)據(jù)點間傳遞吸引度和歸屬度消息，通過迭代不段更新吸引度和歸屬度矩陣，直到產(chǎn)生k個高質(zhì)量的exem?plar為止. 通過聚類產(chǎn)生的每一個聚類集合中包含若干條路徑，這些路徑在邊的信息上相似性最大. 因此接下來對這些相似路徑的布魯姆編碼執(zhí)行按位“與”操作，得到一個復(fù)合布魯姆編碼，此編碼代表一個完整路徑集合，這個集合中的完整路徑具有相似的路徑邊信息. P-tree就是將每一個聚類集合對應(yīng)的布魯姆編碼作為葉子節(jié)點，然后采用自底向上的過程構(gòu)建的，一層一層構(gòu)建，直到只有一個根節(jié)點為止，圖1展示了P-tree構(gòu)建過程.

圖1 P-tree構(gòu)建過程

2 元組壓縮與檢索算法

P-tree索引樹的每個葉子節(jié)點都會對應(yīng)一組相似的完整路徑，這些完整路徑擁有相似的路徑邊信息.當(dāng)將SPARQL分解為完整查詢路徑后，通過對P-tree執(zhí)行自頂向下的邏輯“與”運算找到匹配的葉子節(jié)點時，相當(dāng)于在眾多的完整路徑中找到了與之匹配的路徑信息. 為了得到最終的查詢結(jié)果，還需要將葉子節(jié)點所對應(yīng)的全路徑集合與查詢路徑進行精確匹配. 本部分將依據(jù)相似完整路徑具有的相同邊信息設(shè)計一個元組壓縮和檢索算法CRK2-triples，該算法利用k2-tree壓縮存儲每一個路徑邊所對應(yīng)的元組集合.

由于每一個葉子節(jié)點都包含一組相似的完整路徑集合，這些完整路徑包含的路徑邊有很大的相似性. 因此每一個謂語都會對應(yīng)著一個元組集合. 當(dāng)將RDF圖分解為完整路徑時，一個元組有可能出現(xiàn)在多條完整路徑中，因此就會產(chǎn)生很多元組副本. 為降低副本冗余，通過聚類完整相似路徑已經(jīng)將具有相同邊的元組聚類到一起，在對元組進行存儲時，利用k2-triples進一步將具有相同邊的元組進行統(tǒng)一的壓縮存儲，可以進一步降低元組的副本率. 其中每一條邊所對應(yīng)的元組集合采取的是二級壓縮模式，一級壓縮是建立在k2-triples基礎(chǔ)上實現(xiàn)的，二級壓縮采取RLE（Run-length encoding）方式.

k2-triples是一種專門針對共享屬性的元組設(shè)計的元組壓縮存儲方式，其基本思想是建立在k2-tree基礎(chǔ)上的. k2-triples利用一個位矩陣存儲具有相同屬性元組，其中位矩陣的行和列分別對應(yīng)元組的主語和賓語. 當(dāng)位矩陣中任意位所對應(yīng)的主語和賓語存在時，將其設(shè)置為1，否則設(shè)為0. 對于生成的位矩陣，存在大量主語和賓語的不關(guān)聯(lián)關(guān)系，所以位矩陣中會有大量0出現(xiàn). 如果直接采用位矩陣進行存儲，非常浪費存儲空間. 為此，k2-triples將位矩陣轉(zhuǎn)換成一個k2-tree進行壓縮存儲，圖2描述了位矩陣采用k2-tree的存儲方式。

圖2 k2-triples壓縮方案

當(dāng)k為2時，將位矩陣分成k2個子矩陣，k2-tree的根節(jié)點包含k2個子節(jié)點，對k2子矩陣按自上而下，自左向右順序依次判斷每個矩陣，如果子矩陣中的各個位都為0，則k2-tree的子節(jié)點對應(yīng)為0，否則為1. 如圖2所示，左側(cè)矩陣分解為4個子矩陣時，第3個子矩陣中全部為0，因此對應(yīng)k2-tree節(jié)點即為0. 當(dāng)?shù)谝粚庸?jié)點生成后，對應(yīng)值為1的節(jié)點繼續(xù)重復(fù)上述步驟，直到節(jié)點值為0或者分割矩陣元素個數(shù)為k2為止.

生成的k2-tree，按照從根節(jié)點到葉節(jié)點，從左到右的順序?qū)⑺泄?jié)點值連接成一個二進制的壓縮位串. 同樣，壓縮位串中仍然有很多連續(xù)的1或0，為了縮小存儲空間，繼續(xù)對這個位串利用RLE進行壓縮.如圖2，經(jīng)過一級壓縮后形成的位串為1101011010010101001100110010001000010010，二級壓縮后為“［1］2 1 1 1 2 1 1 2 1 1 1 1 1 2 2 2 2 2 1 3 1 4 1 2 1 1”.

當(dāng)已知檢索謂語時，需要在上述的壓縮串中根據(jù)已知主語查找對應(yīng)賓語，或者已知賓語查找對應(yīng)主語. 以檢索主語為例，壓縮串檢索算法步驟如下：

步驟1：判斷檢索主語與矩陣中哪些子矩陣相關(guān)，同時記錄關(guān)聯(lián)子矩陣對應(yīng)列的起始位置；

步驟2：在壓縮串中獲取子矩陣壓縮串，同時尋找主語對應(yīng)的子矩陣；

步驟3：重復(fù)上述方法，當(dāng)搜索到葉子節(jié)點為1，并且滿足與主語關(guān)聯(lián)，則此列對應(yīng)賓語即為與主語關(guān)聯(lián)的元組的賓語.

3 實驗

本文將P-tree索引和CRK2-triples壓縮和檢索算法同RDF-3X（v0.3.8），Bitmat［16］和TripleBit在合成和真實數(shù)據(jù)集上進行了實驗.

3.1 數(shù)據(jù)集及環(huán)境設(shè)置

本部分選擇LUBM、SP2Bench合成數(shù)據(jù)集和Uniprot真實數(shù)據(jù)集，同時這三種數(shù)據(jù)集又對應(yīng)設(shè)計了相應(yīng)的標(biāo)準(zhǔn)查詢測試語句，表1 給出了每個數(shù)據(jù)集的詳細(xì)信息. 本文利用C++程序設(shè)計語言編寫索引生成代碼，用G++編譯，選擇O2優(yōu)化等級進行優(yōu)化. 運行環(huán)境PC機配置：Intel Xeon 2.00 GHz處理器，20 GB內(nèi)存.考慮到緩存，本文每個查詢都執(zhí)行三次，取平均結(jié)果以避免OS的影響.

表1 數(shù)據(jù)集

3.2 查詢性能

表2和表3顯示了幾種索引存儲方案在LUBM數(shù)據(jù)集上執(zhí)行SPARQL查詢反應(yīng)時間. 從表中可以看出，本文的編碼索引樹P-tree與CRK2-triples的查詢反應(yīng)時間，尤其是在執(zhí)行復(fù)雜查詢時的時間效率比其它三種索引結(jié)構(gòu)更有優(yōu)勢. 分析原因：（i）本文基于完整路徑構(gòu)建的P-tree索引是一種路徑邊的組合索引，通過它可以過濾大量不相關(guān)元組，縮小檢索范圍；（ii）本文提出的壓縮存儲及其對應(yīng)存儲模式下的直接檢索，使相同內(nèi)存情況下CRK2-triples加載更多的查詢數(shù)據(jù)，降低了I/O代價；另外，基于完整路徑的檢索，使大多數(shù)連接僅發(fā)生在很小一部分元組中間，也降低了最終結(jié)果連接的數(shù)量，同時提高了查詢效率.

在表2和表3數(shù)據(jù)顯示P-tree檢索大規(guī)模數(shù)據(jù)集時更有效. 如LUBM50和LUBM2000數(shù)據(jù)集執(zhí)行結(jié)果中，采用RDF-3X索引查詢時間跳躍性很大，尤其是復(fù)雜查詢Q1和Q3. 但CRK2-triples的最大變化卻很平穩(wěn). 原因是RDF-3X需要解壓加載多種索引，當(dāng)數(shù)據(jù)增加時，時間代價變大. 而基于元組的Bitmat和TripleBit，產(chǎn)生的中間結(jié)果要高于CRK2-triples，因此查詢性能也就低于CRK2-triples.

表2 LUBM50查詢反應(yīng)時間（秒）

表3 LUBM2000查詢反應(yīng)時間（秒）

Unirpot數(shù)據(jù)集的元組規(guī)模達到7億條. Bitmat使用本文提供的硬件環(huán)境得不到查詢結(jié)果. 因此表4只對比了RDF-3X、TripleBit和STLIS三種方法的查詢時間. 由于很多元組之間的連接操作是在執(zhí)行P-tree檢索后的路徑集合中完成的，導(dǎo)致參與連接的中間結(jié)果集很小，所以同基于元組的過濾相比，CRK2-triples在路徑模板樹的過濾效果要好于其它兩種.

表4 Uniprot查詢效率（秒）

我們同樣在數(shù)據(jù)集SP2Bench上執(zhí)行查詢，表5列出了各個查詢的執(zhí)行時間. 由于SP2Bench數(shù)據(jù)集規(guī)模很小，大多數(shù)查詢的中間結(jié)果都能一次性加載入內(nèi)存，因此STLIS執(zhí)行查詢的優(yōu)勢沒有在LUBM數(shù)據(jù)集上明顯，由此也驗證了STLIS對大規(guī)模數(shù)據(jù)集的有效性.

表5 SP2B-100M查詢效率（秒）

3.3 存儲空間對比

本文比較了四種索引的存儲空間，本文存儲空間包含存儲數(shù)據(jù)集和索引所消耗的存儲空間. 除了Bitmat，其它的三個索引方案中均包含節(jié)點的字典工具. 表6列出了各存儲方案在不同數(shù)據(jù)集上所消耗的存儲空間. 其中在所有數(shù)據(jù)集上，CRK2-triples所耗費的存儲空間都低于RDF-3X. 原因是RDF-3X包含6個聚類索引和9個聚集索引，因此，RDF-3X是一種以空間換時間的索引. 另外，隨著數(shù)據(jù)規(guī)模的增加，RDF-3X和Bit?mat存儲空間較CRK2-triples增加迅速. 因而CRK2-triples更加合適大規(guī)模數(shù)據(jù). LUBM和SP2Bench的謂語數(shù)量較小導(dǎo)致分解后的完整路徑相似性較大，降低了元組副本量，所以CRK2-tree和TripleBit在這兩個數(shù)據(jù)集上的存儲空間相差不大.

表6 存儲空間（GB）

4 結(jié) 論

本文針對基于元組模式索引知識圖譜時產(chǎn)生的頻繁連接和數(shù)據(jù)冗余問題，提出一種基于路徑檢索的索引樹P-tree. P-tree通過分解RDF有向圖，得到從源點到匯點的完整路徑，然后利用完整路徑邊信息結(jié)合布魯姆過濾器生成路徑編碼，再針對路徑編碼相似性實現(xiàn)相似完整路徑的聚類. 對每一個聚類集合，結(jié)合位運算生成索引樹葉子節(jié)點，采用自底向上方式構(gòu)建而成. 對于索引樹葉節(jié)點對應(yīng)的相似完整路徑集合，本文利用k2-tree實現(xiàn)元組的壓縮存儲，并給出基于CRK2-trriples索引的元組精確匹配.

在實驗中，將所提出的P-tree索引樹及CRK2-triples同現(xiàn)有基于元組的索引存儲方案在時間和空間性能上進行對比. 實驗結(jié)果表明本文提出的索引方案在處理大規(guī)模復(fù)雜查詢時更有效. 同時，CRK2-triples的壓縮存儲方式極大的降低了數(shù)據(jù)存儲空間.