高峰，李秋，顧進(jìn)廣

（1.武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430065；2.湖北省智能信息處理與實(shí)時工業(yè)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，武漢 430065；3.武漢科技大學(xué)大數(shù)據(jù)科學(xué)與工程研究院，武漢 430065；4.國家新聞出版署富媒體數(shù)字出版內(nèi)容組織與知識服務(wù)重點(diǎn)實(shí)驗(yàn)室，北京 100083）

0 概述

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

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

1 相關(guān)工作

數(shù)據(jù)源索引高度總結(jié)原始圖的信息并應(yīng)用于多種下游任務(wù)，而網(wǎng)絡(luò)采樣方法中隨機(jī)節(jié)點(diǎn)、隨機(jī)邊選擇等算法能得到原始圖的部分樣圖。本文采用基于出度加權(quán)的圖采樣算法，為數(shù)據(jù)摘要生成定制樣圖。

1.1 數(shù)據(jù)源索引

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

1.2 圖采樣算法

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

1.3 網(wǎng)絡(luò)采樣算法

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

2 問題及其定義

2.1 數(shù)據(jù)摘要相關(guān)定義

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

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

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

1）唯一性描述信息

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

2）通用性描述信息

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

數(shù)據(jù)摘要中同樣包含樣圖級別的統(tǒng)計(jì)信息：總主語數(shù)，總賓語數(shù)，總?cè)M數(shù)，用于未綁定謂詞時的查詢規(guī)劃。但這并非本文研究的重點(diǎn)，在下文中將忽略相關(guān)的處理。

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

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

2.2 問題定義

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

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

3 近似數(shù)據(jù)摘要的生成模型

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

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

3.1 RDF 圖采樣

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

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

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

1）基本采樣方法

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

2）加權(quán)采樣方法

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

3）混合采樣方法

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

3.2 映射函數(shù)

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

1）基本映射函數(shù)

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

2）改進(jìn)映射函數(shù)

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

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

4 實(shí)驗(yàn)與評估

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

4.1 實(shí)驗(yàn)設(shè)置

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

4.2 近似數(shù)據(jù)摘要生成實(shí)驗(yàn)

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

表1 近似數(shù)據(jù)摘要的生成時間和內(nèi)存開銷Table 1 Generation time and memory overhead of approximate data summarization

4.3 數(shù)據(jù)摘要相似性實(shí)驗(yàn)

4.3.1 評估指標(biāo)

實(shí)驗(yàn)從各個指標(biāo)上量化原始圖直接生成的數(shù)據(jù)摘要D與通過樣圖近似得到的數(shù)據(jù)摘要D′的相似程度。

1）謂詞覆蓋率相似性

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

2）三元組覆蓋率相似性

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

3）能力計(jì)數(shù)相似性

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

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

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

4.3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

圖3 部分?jǐn)?shù)據(jù)集上的Q-error 值分布Fig.3 Distribution of Q-error values on partial datasets

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

通過比較不同的抽樣方法，觀察到加權(quán)方法的估計(jì)精度最低，而基本方法的估計(jì)誤差最小。但是，觀察KEGG 和ChEBI 發(fā)現(xiàn)這兩個數(shù)據(jù)集的Q-error約為其他數(shù)據(jù)集的10 倍?？紤]由樣本量誘導(dǎo)的采樣的三元組覆蓋率相似性，發(fā)現(xiàn)KEGG 和ChEBI 加權(quán)方法捕獲的三元組分別約為基本方法的13 倍和16 倍。對于數(shù)據(jù)分布差異較大的數(shù)據(jù)集，φ1和φ2都不能產(chǎn)生較好的結(jié)果。

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

綜上所述，從采樣方法到RDF 圖的結(jié)構(gòu)，各種因素都會影響近似數(shù)據(jù)摘要的質(zhì)量。因此，在查詢性能實(shí)驗(yàn)中，將研究近似數(shù)據(jù)摘要如何在特定應(yīng)用程序中發(fā)揮作用以及如何影響應(yīng)用程序的性能。

4.4 查詢性能實(shí)驗(yàn)

4.4.1 評估指標(biāo)

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

4.4.2 實(shí)驗(yàn)結(jié)果

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

為獲得準(zhǔn)確查詢時間，在實(shí)驗(yàn)中停用了系統(tǒng)中的ASK 緩存機(jī)制。由于映射函數(shù)φ1和φ2的估計(jì)計(jì)數(shù)精度相差不大，實(shí)驗(yàn)僅給出φ2和φ3的實(shí)驗(yàn)結(jié)果及相應(yīng)分析。表3 給出了查詢性能的相似性指標(biāo)計(jì)算結(jié)果以及LargeRDFBench 所有內(nèi)置查詢的平均源選擇個數(shù)。

表3 查詢性能實(shí)驗(yàn)的相似性指標(biāo)計(jì)算結(jié)果Table 3 Calculation results of similarity index of query performance experiment

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

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

5 結(jié)束語

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