基于圖結構特征采樣數據摘要的聯邦知識圖譜查詢

高峰，李秋，顧進廣

（1.武漢科技大學計算機科學與技術學院，武漢 430065；2.湖北省智能信息處理與實時工業系統重點實驗室，武漢 430065；3.武漢科技大學大數據科學與工程研究院，武漢 430065；4.國家新聞出版署富媒體數字出版內容組織與知識服務重點實驗室，北京 100083）

0 概述

隨著鏈接數據的發展，語義Web 上的RDF 數據集呈現大規模爆炸式增長，其包含的語義信息越來越豐富。對于這些大型語料庫應用程序，亟須研發一種能夠提取數據源概括信息的方法，以使系統做出更快速準確的反饋。近幾年，研究人員提出了多種總結語義圖［1-3］并評估其質量［4-6］的方法，同時在數據集配置文件［7-8］中提取各種特征。然而，一些集中式和分散式的查詢引擎依賴細粒度的數據集描述文件來尋找高效的查詢計劃［9-11］。RDF數據集總結可標準化地表示RDF數據集的一組特征并且有助于處理下游任務［12-14］。CostFed［3］利用聯邦系統中數據集中謂詞的統計數據，通過這些統計數據來選擇三元組模式的相關數據源并對子查詢排序。CostFed方法中的數據摘要捕獲了資源的權威性信息，能夠區分相同URI下的不同數據集，并通過公共前綴，最大程度地捕獲了與謂詞相關的實體信息，同時考慮主語和賓語在謂詞之間的傾斜分布，以不同的方式記錄重要性不同的信息。因此，CostFed 非常適合用于執行有效的基數估計及其他下游任務。雖然數據摘要對應用程序非常有益，但它們的計算可能是一項具有挑戰性的任務。首先，獲取整個數據集來計算這些信息可能過于困難或代價太大。其次，在聯邦查詢中，數據轉儲并不總是可用的［15］，而且數據集只能通過SPARQL 端點或TPF 服務器進行部分訪問［16］。最后，大部分RDF 數據集中實際上只有很少的一部分（不到2%）的三元組用來回答查詢［17］，因此訪問和處理來自所有聯邦成員的全部數據對數據集生成通用索引是非必要的。

本文提出一種基于樣圖來生成近似數據摘要的方法，其僅依賴于原始數據集的一個樣本，與CSPF［11］的技術思路類似，但更關注從樣圖中提取原始圖的數據摘要。通過指定一個RDF 圖，采樣實體并計算謂詞相關統計信息來構建樣本的數據摘要。使用映射函數推斷在樣本中觀察到的特征來近似原始圖的數據摘要。為在近似的數據摘要上盡可能地還原謂詞p的主語和謂語分布信息，需要將p的主語和謂語盡可能完整地捕獲到樣圖上。

1 相關工作

數據源索引高度總結原始圖的信息并應用于多種下游任務，而網絡采樣方法中隨機節點、隨機邊選擇等算法能得到原始圖的部分樣圖。本文采用基于出度加權的圖采樣算法，為數據摘要生成定制樣圖。

1.1 數據源索引

ELLEFI 等［18］為數據集源索引文件中表示的數據集特性提供了一種分類方法，其中包括一般類別、定性類別、來源類別、鏈接類別、許可類別、統計類別和動態類別。為實現高效的RDF 數據結構、索引和壓縮，FERNANDEZ 等［19］結合了RDF 圖的特殊性，提出各種度量方法來表征RDF 數據集。AUER 等［20］提出一種基于語句流的方法LODStats，其包括32 個模式級統計標準。KHATCHADOURIAN 等［21］結合文本標簽和二分收縮生成RDF 數據集摘要的工具ExpLOD。這些摘要包括類、謂語和互鏈接等統計信息。在本文方法中數據摘要不僅捕獲了上述謂詞、許可等統計信息，而且考慮了謂詞的主語和賓語的不均勻分布。

1.2 圖采樣算法

DEBATISTA 等［22］提出基于樣本的大型且變化數據集的近似特定質量指標。該文作者指出：某些質量指標的精確計算過于耗時，而質量的近似值通常已足夠。因此，其應用蓄水池采樣，并使用采樣的三元組來估計URI 和與外部數據提供者的鏈接的可參考性。為獲得包含與典型SPARQL 查詢相同數量原始答案的樣本：RIETVELD 等［17］重寫RDF 圖以計算節點的網絡度量PageRank、入度和出度，并選擇所有三元組中的前k個作為圖的樣本；SOULET 等［23］主要關注分析查詢，這些查詢通常成本較高，無法直接在SPARQL 端點上執行，因此通過在數據集的隨機樣本上執行這些查詢來降低查詢復雜度。這兩種方法都需要本地訪問整個數據集以生成樣本，本文方法與其類似，在一些具有大型且變化數據集的分布式場景中無法對每個數據集進行本地訪問，但本文的目標是對數據進行采樣，以便使用單個樣本來估計數據摘要的統計計數，而不依賴于重復采樣所引起的收斂性。

1.3 網絡采樣算法

LESKOVEC 等［24］概述了適用于從大型網絡中獲取代表性樣本的方法：通過選擇隨機節點，選擇隨機邊或通過探索。為了評估樣本的代表性，使用靜態圖模式，即結構網絡特性的分布。原始圖和樣本之間的圖模式一致性由Kolmogorov-Smirnov D-statistics 指標確定。在該文的實驗結果中沒有得到最佳方法，其性能取決于具體的應用。RIBEIRO 等［25］專注于有向圖，并提出一種有向無偏隨機游走算法（DURW）。將有向圖建模為無向圖，這樣在執行隨機游走時，邊也可以向后遍歷。將隨機跳躍合并到節點，其概率取決于節點的向外度以及邊的權重。與這些方法相比，本文方法旨在生成具有代表性的樣本，以近似RDF 數據集的數據摘要，因此，采樣方法需要針對此任務和RDF 圖的特殊性進行定制。

2 問題及其定義

2.1 數據摘要相關定義

數據摘要在考慮了資源的偏差分布后的具體做法是：1）對一個謂詞所連接的所有主語和賓語的頻率降序排序；2）在降序的頻率序列中迭代地找出3 個切割點，每個切割點都是當前序列中落差最大之處（第1 個切割點定義為0）；3）在3 個切割點的劃分下，資源被分為高、中、低頻3 個桶，分別表示為b0、b1、b2，3 個桶的資源總數上限為100。

在數據摘要中，通過以下統計信息來表示一個謂詞p0或者數據源的描述能力（capability），具體示例如圖1 所示：

圖1 數據摘要的描述能力示例Fig.1 Example of descriptive ability of data summary

1）唯一性描述信息

表示謂詞的URI全稱。中的存儲按分桶類型存儲不同桶中的主語：對b0的主語存儲其URI 及頻率；對b1的主語，存儲其平均頻率；對b2的主語忽略，不存儲。這里的頻率是指僅謂詞和主語綁定下的三元組個數。＜ds：topObjs＞表示按分桶類型存儲不同桶中的賓語。

2）通用性描述信息

存儲在謂詞p0綁定的情況下各個公共前綴及URI 包含該前綴的主語個數。將所有主語的URI 表示為前綴樹，在分支因子大于預設值（如1）時，將該分支因子作為結束節點。取從根節點到結束節點的路徑為公共前綴。＜ds：objPrefixes>存儲以與相同的方法分割的賓語前綴信息。＜ds：distinctSubjs＞、＜ds：distinctObjs>指與p0相關的唯一主語、賓語數。＜ds：triples>表示與p0相關的總三元組個數。

數據摘要中同樣包含樣圖級別的統計信息：總主語數，總賓語數，總三元組數，用于未綁定謂詞時的查詢規劃。但這并非本文研究的重點，在下文中將忽略相關的處理。

定義1一個數據源G的數據摘要D對不同謂詞的描述能力的集合，即D(G)={ccapability}(p)|p∈S。聯邦查詢系統Λ的數據摘要D(Λ)是對系統中多個數據源的描述，D(Λ)={D(G)|G∈Λ}。

定義2通用性描述信息集合表示為L。

2.2 問題定義

由于訪問整個數據集以生成其數據摘要可能太困難或是成本太高，例如，當數據集只能通過SPARQL 端點或TPF 服務器部分訪問時，分布式查詢可能就屬于這種情況，因此為了解決這個問題，本文提出數據摘要近似概念，其目的是利用原始數據集的有限數據來生成近似的原始數據摘要。目標是生成一個近似的數據摘要，盡可能類似于原始數據摘要，但同時只需要訪問部分數據。在該工作中，依賴于原始RDF 圖的樣本，并使用映射函數來估計真實的計數。

定義3給定一個RDF 圖G，映射函數φ，一個子圖S?G，以及S的數據摘要D（S），那么G的近似數據摘要D′(G)為：D′(G)=φD(S)。在理想情況下，近似數據摘要與真實數據摘要中的各個計數對應相同。然而，此類近似方法與原始特征的相似性受到待估計的計數類型、子圖S和映射函數φ的影響。因此，本文基于子圖S和映射函數φ生成近似的數據摘要，最大化了各項計數上與原始RDF 圖的數據摘要的相似性。

3 近似數據摘要的生成模型

圖2 給出了近似數據摘要的生成流程，首先基于CSPF 將采樣應用于索引生成［11］，從原始圖G中抽取一個樣圖S?G。然后從S中生成所有謂詞的描述信息集合，即數據摘要D(S)={ccapability(p)|p∈S}，通過映射函數φ計算出近似的數據摘要D′(G)。最后匯總得到聯邦系統中數據源索引文件。本節重點介紹RDF 圖采樣方法和由樣圖的數據摘要到原始圖的近似數據摘要的映射方法。

圖2 近似數據摘要的生成流程Fig.2 Procedure of approximate data summary generation

3.1 RDF 圖采樣

＜s，p，o＞表示一個三元組，其中，s為主語，p為謂詞，o為賓語，s、o統稱為實體，由謂詞將兩者連接起來。在謂詞很少的情況下，RDF 數據集中三元組的信息也可能很豐富，如LargeRDFBench［26］的其中一個數據集LinkedTCGA，唯一謂詞數僅6 個，但三元組數有4 億多個［22］。因此，本文方法首先是獲得一個原始RDF 圖的代表性樣圖，這為估計數據摘要提供了基礎。為找到這個代表性樣圖，使用隨機節點選擇特定的節點（即RDF圖的實體）進行采樣。在選擇一個實體之后，該實體相關的所有三元組都被并入樣圖。

數據摘要是對謂詞相關主語和賓語的總結，也就是數據摘要對具有相同謂詞的三元組能表現出更佳的總結能力。在出度或入度較高的實體的子圖上，本文方法能獲得更多的三元組。因此，筆者嘗試基于出度和入度加權采樣方法，但在本文的前期工作中，筆者觀察到基于入度加權的方法表現很差，原因是選取到rdf：type 等公共謂詞的賓語后，相關三元組會極大地增加樣圖的容量，并導致超時或內存溢出，而基于出度加權的方法可避免該問題。

由于找到一個相關樣本是一個多目標優化問題，即選擇一個足夠小的樣本，同時仍能實現足夠高的召回率。為了找到相對有效的采樣方法，本文將要采樣的對象定義為給定圖G中的實體集E={s|(s,p,o)∈G}，并設定3 種以實體為中心的采樣方法。這些采樣方法是以G的一個樣本量n為輸入，其輸出是一個由G的n個實體導出的子圖S。假設E1?E為|E1|=n的采樣實體集，那么樣圖S={(s,p,o)|(s,p,o)∈G∧s∈E1}。同時，設定不同的采樣概率以在采樣期間探索搜索空間的不同部分。

1）基本采樣方法

在基本采樣方法中，每個實體e被采樣到的概率是一致的，如式（1）所示。實體是否被采樣是獨立的，與是否受用戶偏向無關。

2）加權采樣方法

加權采樣方法是一種有偏采樣方法，其中實體成為樣本一部分的概率與其出度成正比。因此，實體在圖中的中心度越高，就越有可能成為樣本的一部分，即在主語位置出現多個三元組的實體被選中的概率更高。理論上，該方法只是提高出度高的實體被采樣的概率，但不能保證它們中的每一個都能被采樣到。給定deg+(e)=|{(e,p,o)|(e,p,o)∈G}|表示實體e的出度，那么e被采樣的概率計算如式（2）所示：

3）混合采樣方法

在一個平衡參數α的調和下，試圖找到基本采樣方法和加權采樣方法的最佳組合。在原始圖中，使用加權采樣方法選擇α·n個實體，使用基本采樣方法選擇(1-α)·n實體。在這種情況下，實體e被選擇的概率計算如式（3）所示：

3.2 映射函數

映射函數的目標是從樣圖數據摘要生成原始圖的數據摘要。由于采樣過程選中一個實體時，會選取它所有相關的三元組，因此樣圖數據摘要的唯一性描述信息具有不可映射的特點。本文僅對通用性描述信息進行映射，對定義2 中所有計數C進行同等程度的放大。

1）基本映射函數

對于直接通過樣圖生成的數據摘要D1中的所有計數C，按照原始圖與樣圖的三元組比例映射為原始圖的近似數據摘要D′中的相應計數，如式（4）所示：

2）改進映射函數

考慮到原始圖G中實體的不均勻分布，引入一個更細粒度的比值d來減少基數的高估。當C取值為＜ds：distinctSubjs＞或＜ds：subjPrefixes＞中的計數時，d取該描述能力中唯一主語數（＜ds：distinctSubjs＞）與三元組數（＜ds：triples＞）的比值。類似地，當C取值為＜ds：distinctObjs＞或＜ds：objPrefixes＞中的計數時，d取該描述能力中唯一賓語數（＜ds：distinctObjs＞）與三元組數（＜ds：triples＞）的比值。C取值為其他時保持基本映射函數不變，如式（5）所示：

此外，為充分考慮映射函數對查詢基數估計的影響，設計一個對照組，即將樣圖S的所有計數直接用于下游任務，如式（6）所示：

4 實驗與評估

本節介紹實驗使用的測試集和環境設置，以及設計3 個實驗分別研究在不同采樣方法下近似數據摘要生成過程所需時間和內存開銷、基于不同采樣方法和映射函數生成的近似數據摘要的相似性、基于不同采樣方法和映射函數生成的近似數據摘要作為索引文件對聯邦系統的查詢正確率和時間的影響。將CostFed 作為本文方法對比的基線，并實現了基于采樣生成的近似數據摘要的聯邦查詢系統。

4.1 實驗設置

在實驗中使用聯邦查詢基準測試集LargeRDFBench［26］來驗證本文方法的有效性。LargeRDFBench 內置了25 個查詢，其中，14 個（CD1～CD7、LS1～LS7）用于SPARQL 端點聯合方法，其他11 個查詢（LD1～LD11）用于鏈接數據聯合方法。LargeRDFBench 的9 個數據集分別加載到9 個單獨的Virtuoso 7.1 服務中，并部署在一臺配備了3.2 GHz i7處理器、16 GB RAM和100 GB硬盤的服務器上。對于LargeRDFBench 內置的25 個查詢，每個查詢執行10 次，結果取平均值。在實驗中對選取的數據集進行如下操作：1）生成對應的原始數據摘要；2）按3 種不同的樣本量采樣，由于數據摘要的統計信息需要更多的信息，且所用數據集的三元組個數足夠多，因此設置采樣的實體比例為0.1%、0.5%、1%；3）按照3 種映射函數生成近似的數據摘要；4）在3 個數據摘要相似性指標和2 個運行時指標上進行評估，取α=0.5。

4.2 近似數據摘要生成實驗

表1 給出了基于映射函數φ2的近似數據摘要生成結果，其中，AST 表示平均采樣時間，AGT 表示平均摘要生成時間，TT 表示總耗時，size 表示索引文件大小，W 表示加權采樣方法，H 表示混合采樣方法，B表示基本采樣方法。由表1 可以看出，在1%采樣量和基本采樣配置下平均摘要生成時間最慢，約0.6 h，本文方法比基線方法（在本文實驗配置下原始數據摘要平均生成時間為2 h）最低節省了70%的摘要生成時間。在1%采樣量和加權采樣配置下，生成的索引文件最大，為4.620 MB，即本文方法比基線方法（9.550 MB）最低減少52%的存儲空間。聯邦引擎檢索索引文件的時間因系統配置而異，在配置較高的情況下，檢索時間仍可以忽略不計，因此文件大小對系統性能的影響不是最重要的，而其統計的計數準確性更重要。

表1 近似數據摘要的生成時間和內存開銷Table 1 Generation time and memory overhead of approximate data summarization

4.3 數據摘要相似性實驗

4.3.1 評估指標

實驗從各個指標上量化原始圖直接生成的數據摘要D與通過樣圖近似得到的數據摘要D′的相似程度。

1）謂詞覆蓋率相似性

由于樣本大小的限制，采樣過程中可能會丟失部分謂詞，因此計算在原始圖直接生成的D與近似的D′在原始圖G上的謂詞覆蓋率相似性，如式（7）所示，其中D在原始圖上的謂詞覆蓋率為100%。

2）三元組覆蓋率相似性

數據摘要通過相關主語和賓語的計數來描述謂詞，因此采樣圖中包含一個謂詞在原始圖中主語或謂語的數量越多，數據摘要越能準確描述該謂詞。三元組覆蓋率相似性指標反映了近似的數據摘要中主語和賓語對原始圖的涵蓋情況，定義為D′涉及到的三元組個數與原始數據摘要D涉及到的三元組總數之比，如式（8）所示：

3）能力計數相似性

由于原始圖中實體的分布，因此導致估計計數的準確性具有很大的挑戰性。在一個謂詞的描述能力中，有的計數可能會被準確估計，而有的則可能被嚴重低估或高估。q-error 是真計數和估計數之間比值的最大值［27］。q-error 越高，表示真實值與估計值之間的差異越大，q-error 誤差為1，表示估計是正確的。為觀測估計計數的準確性，給出q-error 的計算公式如式（9）所示：

其中：v和v2分別是D與D′描述能力中的同一種計數C的值。描述能力中包含多個計數，將這些計數的q-error聚合為描述能力的q-error，計算公式如式（10）所示：

q-error 僅測量估計誤差的大小，但并不表明值是高估還是低估。因此，當聚合給定描述能力集合P上的計數相似性時，該屬性將被高估的計數與被低估的計數相互抵消。描述能力的計數相似性定義如式（11）所示：

4.3.2 實驗結果

表2 給出了不同采樣量下3 種采樣方法的謂詞覆蓋率相似性（-δpc）和三元組覆蓋率相似性（-δtc）。比較不同的樣本量，結果顯示在所有情況下，隨著樣本量的增加，相似性指標有所提高。更重要的是，觀察到改進程度取決于原始圖的性質。在大部分圖中，盡管三元組數在劇烈下降，不同樣本量下近似的數據摘要都能做到謂詞的高度或完全覆蓋，但在SWDF 數據集中，實驗所設的最大樣本量也不能收集其60%的謂詞，對于這類數據集，基于采樣生成數據摘要的方法效果更不理想。

表2 謂詞覆蓋率相似性和三元組覆蓋率相似性計算結果Table 2 Calculation results of predicate coverage similarity and triple coverage similarity

比較不同的采樣方法，結果顯示在多數情況下，混合采樣方法次于加權采樣方法且優于基本采樣方法。在不同的采樣量下，加權方法通常能獲得更多的三元組，混合方法次之，基本采樣方法獲得的三元組最少且比例上與采樣量接近。更重要的是，加權方法的優勢在更小的樣本量上更明顯。

例如，在KEGG 數據集中，在0.1%樣本量下，加權方法獲取到的三元組數是基本方法的32 倍，而在1%樣本量下這個比值為16。但是，加權方法在鏈接數量更少的圖上效果越佳。例如，在大數量級的GeoNames數據集上，不同采樣方法的效果相當，而在數量級更小的ChEBI 數據集和KEGG 數據集上，加權方法明顯優于其他方法。

圖3 給出了部分RDF 圖、采樣方法、樣本量和映射函數的結果。在10 個樣圖上生成計數相似性的平均值Q-error，即給定10個樣本的描述能力集合P，如式（12）所示。由于能力計數相似性直接與Q-error 相關，為更加直觀，評估時使用Q-error 而不是。

圖3 部分數據集上的Q-error 值分布Fig.3 Distribution of Q-error values on partial datasets

與表2 中的兩個指標結果類似，Q-error 結果表明，樣本量越大，估計值的誤差越小。對于不同映射函數：首先觀察到φ1和φ2相對于φ3提升了10～100倍；其次觀察到φ2相對于φ1在中位數上平均減少了8.4% 的估計誤差，具體而言，φ2除在Jamendo、Drugbank 數據集上表現差于φ1外（中位數分別平均增加了1.4%和1.3%），其他數據集上都表現更好；最后對于映射函數φ1和φ2，觀察到增加樣本量并不一定會減少Q-error。

通過比較不同的抽樣方法，觀察到加權方法的估計精度最低，而基本方法的估計誤差最小。但是，觀察KEGG 和ChEBI 發現這兩個數據集的Q-error約為其他數據集的10 倍。考慮由樣本量誘導的采樣的三元組覆蓋率相似性，發現KEGG 和ChEBI 加權方法捕獲的三元組分別約為基本方法的13 倍和16 倍。對于數據分布差異較大的數據集，φ1和φ2都不能產生較好的結果。

由所有數據集的計算Q-error 的結果可知，樣本量的增加導致Q-error 降低。在大多數情況下，基本采樣方法產生的Q-error最低，而φ2顯示了平均Q-error的最佳結果（較低中位數）。

綜上所述，從采樣方法到RDF 圖的結構，各種因素都會影響近似數據摘要的質量。因此，在查詢性能實驗中，將研究近似數據摘要如何在特定應用程序中發揮作用以及如何影響應用程序的性能。

4.4 查詢性能實驗

4.4.1 評估指標

與原始數據摘要相同，任何一個資源都可能被生成的近似數據摘要收集（字面量和空值除外），但由于樣本的不完整性以及摘要生成算法的分桶機制，一些重要的資源可能會在收集過程中遺漏，從而影響源選擇和查詢規劃等下游任務。本文提出兩個簡單的指標來評估生成的近似數據摘要對聯邦系統運行時的影響：1）相對執行時間δex=基于近似數據摘要的平均查詢時間/基線平均查詢時間，在相對執行時間為1 的情況下，生成的近似數據摘要和原始數據摘要表現一致，相對執行時間越高，則說明使用近似的數據摘要輔助的聯邦系統的查詢時間越快；2）結果正確率δrc=基于生成的近似數據摘要的查詢結果數/實際查詢結果數，當實際結果數為0 時，δrc取1（理論上，在2 種情況下的結果數都為0），當結果正確率為1 時，本文方法能查詢到完整的結果。

4.4.2 實驗結果

在10 種實驗配置（3 種樣本量、3 種采樣方法和1 種基線方法）上對25 個基準查詢語句（表示為集合Q）中的每一個查詢執行10 次，取平均執行時間為一個查詢語句的執行時間，并計算這些語句的平均相對執行時間δex及平均結果正確率δrc，如式（13）和式（14）所示：

為獲得準確查詢時間，在實驗中停用了系統中的ASK 緩存機制。由于映射函數φ1和φ2的估計計數精度相差不大，實驗僅給出φ2和φ3的實驗結果及相應分析。表3 給出了查詢性能的相似性指標計算結果以及LargeRDFBench 所有內置查詢的平均源選擇個數。

表3 查詢性能實驗的相似性指標計算結果Table 3 Calculation results of similarity index of query performance experiment

由表3 可以看出，對于使用通過映射樣圖的數據摘要而生成的近似數據摘要，聯邦查詢系統能更準確地得到多數查詢結果。通過比較不同采樣量發現，采樣量較大的近似數據摘要得到了更多的正確查詢結果，同時整體上消耗更多時間，并且隨著采樣量減少到0.1%，耗費時間也逐漸增加。通過對比φ2方法下選擇的源個數發現當0.1%采樣量配置時，平均源選擇個數比基線方法約少0.8 個，而該值在1%采樣量下約為0.3 個。通過比較不同的采樣方法發現，加權方法效果最佳，在1%采樣量和加權方法的配置下能到達99.60%的最高正確率。此外，0.5%采樣量和加權方法的這種配置能得到98%的最高正確率，同時在執行時間上優于前一種配置和基線方法。通過對比不同的映射方法發現，φ2和φ3的結果正確率在1%采樣量下相差不大，但隨著樣本量減小，這種差別逐漸變大。此外，不同映射函數對查詢執行時間的影響可以忽略不計（平均變化在0.05 s內）。對于查詢計劃生成而言，數據摘要生成的計數提供了初始的謂詞間的相對關系。通過加權采樣方法獲取的樣圖很大程度上反映了這種相對關系，因此在計算三元組模式的基數之后，映射前后相對關系不會變化，但隨著樣本量的減少，這種相對關系的真實性得不到保證，因此結果正確率有所降低。

綜上所述，加權采樣方法獲得的樣圖能捕獲原始圖的更多信息，在1%采樣量的配置下表現出最高的查詢正確性，在0.5%采樣量的配置下在損失部分正確性的同時花費了更少的查詢時間。此外，本文提出的映射函數在樣本量越小的情況下效果越明顯。

5 結束語

知識圖譜規模日益增大，從知識圖譜中充分挖掘語義數據的概括信息有助于提供更快速更準確的聯邦查詢性能。本文利用謂詞與實體的關系獲取數據源關鍵信息并生成數據摘要索引文件，同時通過采樣的方式捕獲關鍵謂詞，并以出度加權強化謂詞的重要性，以此提高數據摘要的表達能力。實驗結果表明，本文方法在1%采樣量和加權方式的配置下能達到99.60%的查詢正確率。后續將分析并研究謂詞多重性等RDF 圖結構特征來抽取概括信息，以更好地捕獲樣圖的關鍵謂詞，進一步擴展本文近似數據摘要生成方法的應用范圍。