• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    基于結(jié)構(gòu)分解的分布式RDF圖模式匹配優(yōu)化算法

    2022-07-12 14:03:50孫云浩邢維康李冠宇李逢雨
    關(guān)鍵詞:謂詞三元組核心

    孫云浩 邢維康 李冠宇 韓 冰 李逢雨

    (大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院 遼寧 大連 116026)

    0 引 言

    如今,由于知識(shí)圖譜的興起,越來越多的數(shù)據(jù)集采用資源描述框架(Resource Description Framework,RDF)的格式發(fā)布和維護(hù)數(shù)據(jù),它將一個(gè)數(shù)據(jù)集表示為一組三元組,這些三元組構(gòu)成一個(gè)有向標(biāo)簽圖。例如Google的知識(shí)圖[1]和一些公共知識(shí)庫DBpedia[2]、Bio2RDF[3]等。Google和Bing等一些商業(yè)網(wǎng)站也通過SPARQL向這些數(shù)據(jù)集提供在線查詢服務(wù)。

    早期的RDF存儲(chǔ),如RDF-3X[4]、SW-Store[5]、HexaStore[6],通常使用集中式設(shè)計(jì)。隨著RDF數(shù)據(jù)集規(guī)模和查詢規(guī)模增加,保證查詢的低延遲性成為了一項(xiàng)挑戰(zhàn)。作為回應(yīng),很多研究致力于開發(fā)可擴(kuò)展和高性能的系統(tǒng)來索引RDF數(shù)據(jù)和處理SPARQL查詢。如StarMR[7]、TriAD[8]、Trinity.RDF[9]、Wukong[10]和Stylus[11]等通過使用分布式存儲(chǔ),來應(yīng)對不斷增長的數(shù)據(jù)量。

    雖然RDF數(shù)據(jù)集能夠以三元組的形式作為元素存儲(chǔ)在關(guān)系表中(即三元組存儲(chǔ))[4,8,12-13],但RDF數(shù)據(jù)集本質(zhì)上是一個(gè)帶標(biāo)簽的有向多邊圖,所以也能夠以原生圖形(即圖形存儲(chǔ))的形式進(jìn)行存儲(chǔ)管理[9,11,14,25]。文獻(xiàn)[10-11]也表明,使用三元組存儲(chǔ)雖然可以方便地繼承很多關(guān)系數(shù)據(jù)庫上成熟的查詢優(yōu)化技術(shù),但查詢處理過度依賴于大表索引所產(chǎn)生中間結(jié)果的連接操作,這通常會(huì)產(chǎn)生大量無用的中間數(shù)據(jù)。此外,使用關(guān)系表來存儲(chǔ)三元組可能會(huì)限制通用性,很難支持RDF數(shù)據(jù)上的其他圖形分析,如可達(dá)性分析、最短路徑和社區(qū)檢測等。

    本文遵從基于圖形的設(shè)計(jì),使用基于內(nèi)存的分布式架構(gòu),將RDF數(shù)據(jù)集存儲(chǔ)為原生圖形式,并利用圖探索策略來處理查詢。由于處理圖探索問題的復(fù)雜性,而將查詢圖Q的節(jié)點(diǎn)分解為核心(Core)、路徑(Path)、邊際(Marginal)節(jié)點(diǎn)三部分,并依據(jù)分解結(jié)構(gòu)提出了一種查詢圖的生成樹模型Tq。使得圖探索過程轉(zhuǎn)化為沿著Q的生成樹Tq迭代地?cái)U(kuò)展從Q到數(shù)據(jù)圖D的嵌入(embedding),同時(shí)檢查與Tq中新擴(kuò)展的節(jié)點(diǎn)相鄰的非樹邊。最后,根據(jù)各部分結(jié)構(gòu)的特征,通過在分布式并行計(jì)算中分割匹配過程及推遲笛卡爾乘積操作,來盡可能縮減查詢的中間結(jié)果數(shù)及增大查詢并行度以降低查詢延遲。

    本文的主要貢獻(xiàn)如下:(1) 根據(jù)查詢圖中各部分結(jié)構(gòu)在分布式環(huán)境中的匹配特點(diǎn),提出了查詢圖的CMP節(jié)點(diǎn)分解模型。針對RDF數(shù)據(jù)圖節(jié)點(diǎn)為語義實(shí)體的特點(diǎn),提出了基于類型的統(tǒng)計(jì)概要圖,并利用統(tǒng)計(jì)信息對節(jié)點(diǎn)分解結(jié)構(gòu)進(jìn)行加權(quán)計(jì)算。(2) 在加權(quán)的查詢圖上,提出了以節(jié)點(diǎn)為核心的代價(jià)模型并結(jié)合最小生成樹思想將復(fù)雜的圖探索問題轉(zhuǎn)化為查詢執(zhí)行樹,得到了更高效的查詢執(zhí)行序列。(3) 為進(jìn)一步提高算法性能,提出了兩種優(yōu)化策略:一是通過推遲笛卡爾積操作,大量壓縮了核心結(jié)構(gòu)匹配時(shí)包含全歷史信息的路徑數(shù)目;二是通過結(jié)構(gòu)分解將匹配過程分割,使得路徑結(jié)構(gòu)匹配可以無冗余計(jì)算地高速并行執(zhí)行。(4) 在基準(zhǔn)合成數(shù)據(jù)集LUBM[26]和真實(shí)數(shù)據(jù)集YAGO2[27]上進(jìn)行了實(shí)驗(yàn),驗(yàn)證了算法的有效性、高效性;針對不同數(shù)據(jù)集規(guī)模及集群節(jié)點(diǎn)數(shù)目的變化進(jìn)行了實(shí)驗(yàn)分析,驗(yàn)證了算法的可擴(kuò)展性。

    1 預(yù)備知識(shí)及相關(guān)工作

    1.1 RDF圖及SPARQL查詢

    定義1RDF數(shù)據(jù)圖。RDF數(shù)據(jù)圖D(V,E,L,φ)是一個(gè)有向標(biāo)簽圖,其中V表示節(jié)點(diǎn)集;E是連接V中節(jié)點(diǎn)的有向邊集;E:(v,v′)是一個(gè)有向函數(shù),表示從v到v′的一條有向邊,其中v,v′∈V;L表示邊和節(jié)點(diǎn)標(biāo)簽集;φ:V∪E→(L∪var)表示一個(gè)將節(jié)點(diǎn)或邊映射到對應(yīng)標(biāo)簽的標(biāo)簽函數(shù)。

    圖1是從LUBM[26]數(shù)據(jù)集中摘取的RDF圖示例。為了更簡潔地表述,對節(jié)點(diǎn)URI進(jìn)行了壓縮表示,沒有涉及RDF標(biāo)準(zhǔn)定義中的空節(jié)點(diǎn)(Blank Node),空節(jié)點(diǎn)問題與本文內(nèi)容是正交的。

    圖1 RDF數(shù)據(jù)圖示例

    SPARQL是W3C推薦的RDF數(shù)據(jù)集的標(biāo)準(zhǔn)查詢語言。最常見的SPARQL查詢類型定義如下:

    Q:SELECTRDWHERETP

    其中:RD是對結(jié)果的描述,TP是一組三元組模式。每個(gè)三元組模式的形式為(簡寫為),其中每一個(gè)主語、謂語和賓語都可以表示為一個(gè)變量或者常數(shù)。給定RDF數(shù)據(jù)圖D,三元組模式TP在D上搜索D的一組子圖,每個(gè)子圖都通過將TP中的模式變量映射到D中的值(節(jié)點(diǎn)或邊)形成綁定,來匹配TP所定義的圖形模式,結(jié)果描述RD包含圖形模式中的變量子集。

    定義2RDF查詢圖。RDF查詢圖Q是SPARQL查詢類型的圖形化表示。SPARQL中的每一個(gè)三元組模式TP可以被看作RDF查詢圖中的一條帶節(jié)點(diǎn)和邊標(biāo)簽的有向邊,與數(shù)據(jù)圖不同的是,查詢圖中的節(jié)點(diǎn)可以是變量指代。所有的三元組模式構(gòu)成的完整圖形即為RDF查詢圖Q(∧1≤i≤nTPi)。

    定義3模式匹配。給定一個(gè)RDF圖D和SPARQL查詢Q(∧1≤i≤nTPi),模式匹配Q(D)定義為:

    (1) 設(shè)f是從Q到D的一個(gè)映射;

    如圖2(a)所示,SPARQL查找選修了由其指導(dǎo)教授所講授課程的學(xué)生及對應(yīng)的選修課程組合。查詢可以圖形化來表示,如圖2(b)所示。圖2(c)中顯示了該查詢在圖1所示的示例RDF圖中的模式匹配結(jié)果Q(D),即結(jié)果描述RD為{?X→Person_B,?Y→Person_A}。

    (a) SPARQL原語 (b) 查詢圖表示Q (c) 結(jié)果描述RD圖2 示例RDF圖上的SPARQL查詢示例

    1.2 現(xiàn)有的解決方案

    本節(jié)介紹最先進(jìn)的RDF系統(tǒng)中所采用的幾種代表性方法。

    1) 關(guān)系方法(scan-join)。大多數(shù)RDF系統(tǒng)將RDF數(shù)據(jù)作為關(guān)系數(shù)據(jù)庫中的一組三元組表進(jìn)行存儲(chǔ)和索引。如Abadi等[5]提出的SW-store將RDF三元組垂直分區(qū)到多個(gè)屬性表。RDF-3X[4]和Hexastore[6]通過直接在B+-tree中冗余地存儲(chǔ)三元組SPO的多種排列(如PSO、POS)來實(shí)現(xiàn)基于索引的查詢方案,這可能導(dǎo)致多達(dá)15個(gè)這樣的B+-tree[15]。Peng等[16]給出了一種能夠根據(jù)查詢負(fù)載優(yōu)化圖劃分和存儲(chǔ)的RDF圖存儲(chǔ)方案,查詢處理通常包括掃描(scan)和連接(join)兩個(gè)階段。在掃描階段,查詢引擎將SPARQL查詢分解為一組三元組模式。例如,對于圖2所示查詢,三重模式TP包含{?X advisor ?Y}、{?X takesCourse ?Z}、{?Y teachOf ?Z}三個(gè)三元組模式。對于每個(gè)三元組模式,通過掃描索引或表來生成符合每個(gè)模式的中間結(jié)果綁定。在連接階段,將掃描階段的中間結(jié)果綁定依照連接計(jì)劃(例如左深連接或者平面連接)進(jìn)行連接,以產(chǎn)生查詢的最終答案。

    2) 基于MapReduce的方法。分布式系統(tǒng)H-RDF-3X[17]和SHARD[18]在多個(gè)計(jì)算節(jié)點(diǎn)上水平劃分RDF數(shù)據(jù),并將Hadoop作為跨節(jié)點(diǎn)查詢的通信層。H-RDF-3X通過最小邊割方法METIS[19]將RDF圖分割成指定分區(qū)數(shù)。然后,在每個(gè)分區(qū)上利用1-hop或者2-hop復(fù)制來擴(kuò)展分區(qū)邊界以保證小直徑查詢可以在分區(qū)內(nèi)部獲取完整答案。兩個(gè)系統(tǒng)的查詢處理都使用迭代的Reduce-side連接,其中Map階段進(jìn)行選擇,Reduce階段執(zhí)行實(shí)際連接[20]。但是對于復(fù)雜查詢,Map階段掃描大量的RDF元組和迭代運(yùn)行MapReduce作業(yè)的開銷十分昂貴。Lai等[21]提出了基于TwinTwig結(jié)構(gòu)分解的MapReduce分布式高效子圖枚舉算法,但該算法僅用于無向無標(biāo)簽圖。S2RDF將SPARQL查詢轉(zhuǎn)換為Spark分布式計(jì)算框架上的RDD操作,其離線建立了大量索引,用于加速在線查詢,但對于大規(guī)模知識(shí)圖譜,索引構(gòu)建時(shí)間開銷可能很高[22]。TriAD[8]中的工作表明,如果分布式查詢過程中需要交互,應(yīng)該避免通過Hadoop進(jìn)行連接。

    3) 原生圖方法。最近許多以原生圖格式存儲(chǔ)RDF數(shù)據(jù)的方法被提出。這些方法通常使用鄰接表作為存儲(chǔ)和處理RDF數(shù)據(jù)的基本結(jié)構(gòu)。此外,這些方法通過使用復(fù)雜的索引,如TripleBit[13]、BitMat[14]和gStore[23],或者使用圖形探索(graph-exploration),如Trinity.RDF[9]和Wukong[10],在進(jìn)行最后的連接操作之前剪枝許多無望形成結(jié)果的三元組。原生圖方法能更有效地支持更多類型的圖形查詢,例如可達(dá)性、社區(qū)檢測、最短路徑及隨機(jī)游走(部分已經(jīng)包含在SPARQL1.1標(biāo)準(zhǔn)中),這也是RDF-S樣式推斷所必須的。Trinity.RDF中只采用一步剪枝的圖探索策略雖然避免了指數(shù)級(jí)路徑結(jié)果的保存,但最終需要利用一臺(tái)機(jī)器來聚合所有片段結(jié)果以對結(jié)果進(jìn)行最終連接。文獻(xiàn)[8,10]中的研究發(fā)現(xiàn),最終的連接很容易成為查詢的瓶頸,因?yàn)樗薪Y(jié)果都需要聚合到一臺(tái)機(jī)器中進(jìn)行連接,Wukong在LUBM[26]上的實(shí)驗(yàn)表明,一些查詢在最終連接上花費(fèi)了90%以上的執(zhí)行時(shí)間。Wukong采用全歷史剪枝的策略來避免最終連接,但其只是借鑒關(guān)系方法中基于謂詞連接的代價(jià)模型來指導(dǎo)查詢執(zhí)行,沒有針對圖探索策略及復(fù)雜查詢結(jié)構(gòu)來進(jìn)行執(zhí)行序列優(yōu)化,也沒有壓縮基于全歷史剪枝策略的中間結(jié)果,造成冗余驗(yàn)證及不必要的網(wǎng)絡(luò)傳輸。

    針對上述問題,本文提出了一種新型的查詢分解模型并以此優(yōu)化查詢執(zhí)行序列,并根據(jù)各部分結(jié)構(gòu)的特征,分割匹配過程及推遲笛卡爾乘積操作,來盡可能縮減查詢的中間結(jié)果數(shù)及增大查詢并行度來降低查詢延遲。

    2 基于結(jié)構(gòu)分解的圖模式匹配

    本節(jié)提出一種基于圖探索模式的新的RDF并行計(jì)算模型,旨在盡早地對匹配過程中的結(jié)果路徑進(jìn)行剪枝并延緩笛卡爾乘積過程。

    2.1 CPM查詢圖分解模型

    為了更好地支持圖探索模式和復(fù)雜查詢,將查詢圖Q中的節(jié)點(diǎn)進(jìn)行分解,根據(jù)查詢圖各部分結(jié)構(gòu)的特征,來盡可能縮減查詢的中間結(jié)果數(shù)及增大查詢并行度以降低查詢延遲。

    定義4無向查詢圖Qud。對于給定的查詢圖Q,將圖中的每一條邊都替換為無向邊,所構(gòu)成的無向圖定義為無向查詢圖(記為Qud)。

    為了方便后續(xù)表述,如圖3所示,將無向圖Q中的查詢節(jié)點(diǎn)標(biāo)示為圓形,并采用類樹形的結(jié)構(gòu)劃分層次。轉(zhuǎn)換成無向圖,是為了泛化原查詢圖中邊關(guān)系的指向,Qud中各層次之間的邊所對應(yīng)的原始邊既可以由低層次指向高層次,也可以由高層次指向低層次。

    圖3 查詢圖Q及其無向查詢圖Qud

    定義5核心節(jié)點(diǎn)集VC。給定查詢圖Qud,對于能完整遍歷Qud中所有節(jié)點(diǎn)的任意生成樹Tq,核心節(jié)點(diǎn)集VC={u|u∈Qud,?(p∈Pre(u),Tq←Qud),p是Tq的非樹邊},其中Pre(u)表示與節(jié)點(diǎn)u關(guān)聯(lián)的謂詞邊,即對于核心節(jié)點(diǎn)中的每一個(gè)節(jié)點(diǎn),都存在一條邊在某棵生成樹中為非樹邊。

    如圖4所示,對于由Qud中節(jié)點(diǎn)?C、?FP、?S構(gòu)成的環(huán)形結(jié)構(gòu),對于不同的查詢圖生成樹Tq,謂詞邊TO、TC、Adv都可能作為非樹邊出現(xiàn),與非樹邊相關(guān)聯(lián)的?C、?FP、?S節(jié)點(diǎn)均為核心節(jié)點(diǎn)。

    圖4 核心節(jié)點(diǎn)集結(jié)構(gòu)

    一個(gè)良好的匹配序列需要盡早進(jìn)行非樹邊的驗(yàn)證,一方面這將修剪大量無法形成最終結(jié)果的路徑綁定(即中間結(jié)果),另一方面也減少了非樹邊緣檢查的總數(shù)。因此,算法將VC中的節(jié)點(diǎn)作為匹配序列的起始部分,這對高效的子圖匹配至關(guān)重要[24]。

    定義6路徑節(jié)點(diǎn)集VP。給定Qud,路徑節(jié)點(diǎn)集VP={u|d(u)≥2,?(至多一個(gè)u′∈Qud.Adj(u),u′∈VC)},其中d(u)表示節(jié)點(diǎn)的度,Qud.Adj(u)表示節(jié)點(diǎn)u的鄰接節(jié)點(diǎn)集,即路徑節(jié)點(diǎn)集包括所有的節(jié)點(diǎn)度大于等于2且至多只與一個(gè)核心節(jié)點(diǎn)相連的節(jié)點(diǎn)。

    如圖5所示,對于無向查詢圖Qud,?R、?D、?P均為路徑節(jié)點(diǎn),VP中節(jié)點(diǎn)在任何生成樹Tq中都不與非樹邊相連,所以在進(jìn)行節(jié)點(diǎn)驗(yàn)證時(shí)并不需要利用到歷史信息,可以減少通信代價(jià)且可以并行化操作。路徑節(jié)點(diǎn)的匹配緊跟在核心節(jié)點(diǎn)之后并行執(zhí)行。

    圖5 路徑節(jié)點(diǎn)集結(jié)構(gòu)

    定義7邊際節(jié)點(diǎn)集VM。給定無向查詢圖Qud,邊際節(jié)點(diǎn)集VM={u|u∈Qud,d(u)=1},即邊際節(jié)點(diǎn)集包括Qud中的所有度為1的節(jié)點(diǎn)。

    如圖6所示,對于無向查詢圖Qud、?RA、?U、?X、?TA均為邊際節(jié)點(diǎn)。在本文的存儲(chǔ)模型中,由于邊際節(jié)點(diǎn)只存在一條謂詞邊約束,所以完全可以在其鄰接節(jié)點(diǎn)上進(jìn)行節(jié)點(diǎn)的匹配驗(yàn)證,而無須將中間結(jié)果傳遞到邊際節(jié)點(diǎn)。邊際節(jié)點(diǎn)的候選集也不會(huì)對后續(xù)的匹配有所幫助,所以作為整個(gè)結(jié)果的笛卡爾積部分,應(yīng)將其放在匹配的最后進(jìn)行處理。

    圖6 邊緣節(jié)點(diǎn)集結(jié)構(gòu)

    2.2 核心節(jié)點(diǎn)匹配序列

    根節(jié)點(diǎn)是匹配順序中的第一個(gè)節(jié)點(diǎn),所以要從核心節(jié)點(diǎn)集VC中選擇根節(jié)點(diǎn)。本節(jié)中,優(yōu)化器結(jié)合對數(shù)據(jù)圖預(yù)處理而生成的RDF特有的統(tǒng)計(jì)概要,對匹配中間結(jié)果進(jìn)行更加準(zhǔn)確的估計(jì),制定更加合理的匹配序列(seq)。

    直觀來講,傾向于選擇具有較少的局部匹配結(jié)果,以及較大的度(只統(tǒng)計(jì)核心節(jié)點(diǎn)內(nèi)部的度)的節(jié)點(diǎn)作為初始節(jié)點(diǎn)。較少的匹配結(jié)果意味著更低的網(wǎng)絡(luò)傳輸代價(jià);較大的度意味著有更多的機(jī)會(huì)在匹配早期階段修剪綁定路徑。類似于文獻(xiàn)[24],本文選擇根節(jié)點(diǎn):

    (1)

    式中:d(u)是u關(guān)聯(lián)到核心節(jié)點(diǎn)內(nèi)部的度;cost(u)是對核心查詢節(jié)點(diǎn)u的預(yù)估局部匹配結(jié)果數(shù)。得到cost(u)有不同的策略,不同的策略會(huì)有不同的代價(jià)。本文使用預(yù)處理階段生成的RDF特有的統(tǒng)計(jì)概要來對進(jìn)行估計(jì)。接下來將討論統(tǒng)計(jì)概要的獲取過程。

    W3C提供了一組詞匯表(作為RDF標(biāo)準(zhǔn)的一部分)來編碼RDF圖豐富的語義信息,例如類型謂詞(rdfs:type)提供了將RDF圖的節(jié)點(diǎn)分組成不同類別的功能。與一般標(biāo)簽圖不同,RDF圖節(jié)點(diǎn)標(biāo)識(shí)的是實(shí)體/文本信息,實(shí)體的語義特性導(dǎo)致了相同類型的節(jié)點(diǎn)通常具有類似的謂詞組合,便于統(tǒng)計(jì)。

    對于每一個(gè)type類型,C(type)表示對應(yīng)數(shù)據(jù)類型的節(jié)點(diǎn)在數(shù)據(jù)圖中的基數(shù)。

    圖7 RDF摘要統(tǒng)計(jì)示例

    對于RDF圖G上的查詢Q,用Pre(u)表示查詢節(jié)點(diǎn)u具有的屬性(也就是謂詞)集合,Pre(u)={pi|?∈Qud}。根據(jù)u′所屬節(jié)點(diǎn)類型集,劃分Pre(u)=P(u)∪P′(u),其中:

    P(u)={pi|?(u′∈VC且(u,pi,u′)∈Qud)}P′(u)={pi|?(u′?VC且(u,pi,u′)∈Qud)}

    進(jìn)一步地,根據(jù)查詢圖Q中謂詞p與u的出入邊關(guān)系,劃分P(u)=P-in(u)∪P-out(u),形式化為:

    P-out(u)={pi|?(u′∈VC且(u,pi,u′)∈Q)}P-in(u)={pi|?(u′∈VC且(u′,pi,u)∈Q)}

    同樣可得,P′(u)=P′-in(u)∪P′-out(u)。

    基于上述討論,得出了起始節(jié)點(diǎn)的局部匹配數(shù)cost(u)的估算公式:

    cost(u)=C(u.type)×des(u)×cut(u)

    (2)

    (3)

    (4)

    通過式(1)-式(2),具有最小代價(jià)的節(jié)點(diǎn)被選為根節(jié)點(diǎn)。例如圖7中示例,核心節(jié)點(diǎn)集VC={u1,u2,u3}中三個(gè)節(jié)點(diǎn)所對應(yīng)d(u)均為2。通過計(jì)算,cost(u1)為1 952,cost(u2)為3 489,cost(u3)為39 124。因此,選取u1節(jié)點(diǎn)為核心節(jié)點(diǎn)中查詢搜索的起始節(jié)點(diǎn)。

    定義8核心結(jié)構(gòu)權(quán)重圖Gw(VC)。給定核心節(jié)點(diǎn)集VC,核心結(jié)構(gòu)圖Gw(VC)中的權(quán)重w計(jì)算為:

    (1) 對于模式Tp=,其中u,u′∈VC。

    式中:Tpcut(u)為核心結(jié)構(gòu)中所有內(nèi)部模式(邊)的選擇度的乘積,權(quán)重值w表示核心節(jié)點(diǎn)在指定邊的預(yù)估計(jì)中間結(jié)果數(shù)。

    對于圖7所示查詢圖及概要統(tǒng)計(jì)圖,計(jì)算得到的核心結(jié)構(gòu)權(quán)重圖如圖8所示。給定起始節(jié)點(diǎn)r,在Gw(VC)上結(jié)合最小生成樹思想得出最低代價(jià)的核心節(jié)點(diǎn)匹配序列,并依次記錄節(jié)點(diǎn)的樹邊與非樹邊。

    圖8 查詢圖的核心結(jié)構(gòu)權(quán)重圖示例

    如算法1所示,算法1-4行將每個(gè)節(jié)點(diǎn)的最低連接代價(jià)key值設(shè)置為∞,然后初始化匹配序列,并將根節(jié)點(diǎn)r的key值設(shè)置為0,以便在循環(huán)中第一個(gè)執(zhí)行;算法5-17行借鑒Prim算法思想尋找以r為起始點(diǎn)的,核心結(jié)構(gòu)權(quán)重圖Gw(VC)上的最小代價(jià)生成樹(即匹配序列)。當(dāng)以一個(gè)二叉最小堆來記錄u.key時(shí),1-4行的時(shí)間成本為O(|VC|);While循環(huán)一共要執(zhí)行|VC|次,其中Extract_Min(Q)操作選擇出隊(duì)列Q中具有最小key值的節(jié)點(diǎn)u并將其移出隊(duì)列,單次操作的時(shí)間成本為O(lg|VC|),所以函數(shù)總的時(shí)間代價(jià)為O(|VC|lg|VC|);算法8-16行的for循環(huán)執(zhí)行的總次數(shù)為O(E),通過對節(jié)點(diǎn)設(shè)置標(biāo)志位可以在O(1)內(nèi)實(shí)現(xiàn)對v∈QorVnt的判斷,算法11行中賦值操作對應(yīng)的堆操作時(shí)間成本為O(lg|VC|)。所以,用E表示Gw(VC)中邊的數(shù)量,總的時(shí)間代價(jià)為O(|VC|lg|VC|+Elg|VC|)=O(Elg|VC|)。

    算法1核心節(jié)點(diǎn)匹配序列(MatchingOrder)

    輸入:核心節(jié)點(diǎn)集VC,匹配根節(jié)點(diǎn)r,核心結(jié)構(gòu)權(quán)重圖Gw(VC)。

    輸出:核心節(jié)點(diǎn)的匹配順序seq。

    1.for each查詢節(jié)點(diǎn)u∈VCdo

    2.u.key←∞;

    3.seq←?;r.key←0;

    4.Q←VC;Vnt←?;

    5.whileQ≠? do

    6.u←Extract_Min(Q);

    7.seq←seq∪u;

    8.for eachv∈Gw(VC).Adj(u) do

    9.ifv∈Q

    10.ifw(u,v)

    11.v.key←w(u,v);

    12.ifv∈Vnt

    13.u.nt←u.nt∪e(u,v);

    14.else

    15.u.t←u.t∪e(u,v);

    16.Vnt←Vnt∪v;

    17.MatchingEdgeOrder(u,u.nt,u.t);

    18.returnseq

    2.3 將查詢圖轉(zhuǎn)化為查詢計(jì)劃樹

    查詢序列確定后,可以將無向查詢圖重構(gòu)為一棵查詢樹(記為Tq)?;趫D探索的RDF存儲(chǔ)結(jié)構(gòu)保證了對同一節(jié)點(diǎn)的鄰接關(guān)系都存儲(chǔ)在與之相同的機(jī)器上。節(jié)點(diǎn)驗(yàn)證及查詢路由(Query Routing)與查詢圖的BFS過程類似,完整的查詢圖只需要在Tq中補(bǔ)全缺失的非樹邊。

    如圖9所示,若查詢圖中核心節(jié)點(diǎn)部分所構(gòu)成的圖形如圖9(a)所示,經(jīng)過計(jì)算選取u1為起始節(jié)點(diǎn),且查詢執(zhí)行序列為seq=,則對應(yīng)的Tq如圖9(b)所示(虛線表示非樹邊驗(yàn)證)。對于Tq中每一個(gè)查詢節(jié)點(diǎn)ui的候選節(jié)點(diǎn),其邊緣的驗(yàn)證順序?yàn)椋悍菢溥?樹邊,多條非樹邊內(nèi)部的順序與多條樹邊內(nèi)部的順序,由根據(jù)統(tǒng)計(jì)概要計(jì)算得出的模式選擇度大小α(Tp)(即定義8中(2)所示)決定,最終得到完整的查詢執(zhí)行計(jì)劃。

    (a) (b)圖9 核心節(jié)點(diǎn)圖G(VC)及查詢計(jì)劃樹Tq

    節(jié)點(diǎn)邊緣匹配順序算法流程如算法2所示。

    算法2節(jié)點(diǎn)邊緣匹配順序(MatchingEdgeOrder)

    輸入:查詢節(jié)點(diǎn)u,節(jié)點(diǎn)的非樹邊集u.nt,節(jié)點(diǎn)的樹邊集u.t。

    輸出:u上的邊緣匹配序列u.order。

    1.u.order←?;

    2.for eachv∈VP.Adj(u) orv∈VM.Adj(u) do

    3.u.t←u.t∪e(u,v);

    4.Whileu.nt≠? do

    6.u.order←u.order∪p;

    7.u.nt←u.nt-{p};

    8.Whileu.t≠? do

    10.u.order←u.order∪p;

    11.u.t←u.t-{p};

    14.returnu.order

    圖10 全歷史剪枝下各中間路徑驗(yàn)證匹配過程

    對于u2的候選節(jié)點(diǎn),u2.nt表示Tq中與u2相連的未匹配非樹邊集合,即邊p4;u2.t表示與u2相連的未匹配樹邊集合,即邊p3。當(dāng)查詢路徑執(zhí)行到u2節(jié)點(diǎn)時(shí),由于u2.nt不為空,固先匹配非樹邊p4,再匹配樹邊p3。圖10中實(shí)線箭頭所示過程為非樹邊驗(yàn)證,虛線箭頭所示部分為樹邊匹配過程。按照核心節(jié)點(diǎn)執(zhí)行序列依次執(zhí)行各節(jié)點(diǎn),直到所有節(jié)點(diǎn)都完成路徑匹配。

    圖11顯示了數(shù)據(jù)圖上依據(jù)v-id進(jìn)行hash分區(qū)的一個(gè)示例,其中虛線節(jié)點(diǎn)代表謂詞或類型所對應(yīng)的虛擬節(jié)點(diǎn)。類似于文獻(xiàn)[10-11],鍵值存儲(chǔ)創(chuàng)建了一個(gè)RDF的圖模型,每個(gè)RDF實(shí)體被表示為具有唯一id的圖節(jié)點(diǎn),節(jié)點(diǎn)id與謂詞id及出入度關(guān)系組成的三元組結(jié)構(gòu)實(shí)現(xiàn)了細(xì)粒度的key值表示,Value表示對應(yīng)索引的候選集合,如圖12所示。這十分便于獲取各查詢節(jié)點(diǎn)的候選集合。

    圖11 數(shù)據(jù)圖分區(qū)示例

    圖12 字典編碼與索引結(jié)構(gòu)

    算法將查詢計(jì)劃傳遞到每一個(gè)計(jì)算節(jié)點(diǎn)。對于變量節(jié)點(diǎn),根據(jù)不同情況,計(jì)算節(jié)點(diǎn)利用類型或者謂詞對應(yīng)的倒排索引(Idx-t,Idx-p)查詢到本地全部的初始根節(jié)點(diǎn)r的候選,在所有計(jì)算節(jié)點(diǎn)上開始匹配任務(wù)。

    2.4 高并發(fā)的子路徑匹配連接算法

    在先前的圖探索方法Trinity.RDF和Wukong中,查詢序列的生成借鑒了關(guān)系方法中的成熟模型,其類似于關(guān)系方法中join階段的連接計(jì)劃確定(例如左深連接計(jì)劃樹),以謂詞關(guān)系的連接順序主導(dǎo)來確定節(jié)點(diǎn)匹配序列。但是,RDF本質(zhì)上是一個(gè)帶標(biāo)簽的有向多邊圖,關(guān)系模型無法充分利用查詢圖的結(jié)構(gòu)特征(例如環(huán)形或者星形結(jié)構(gòu))來指導(dǎo)查詢,無法充分發(fā)揮圖探索策略的優(yōu)勢(即與關(guān)系方法相比,隨著探索的進(jìn)行,在匹配早期修剪大量無望的中間結(jié)果)。

    例如,在圖7(a)所示結(jié)構(gòu)中,若關(guān)系主導(dǎo)的匹配序列為seq=,經(jīng)過謂詞Adv、TO的探索,中間結(jié)果包含由?Student、?FB、?Course候選結(jié)果形成的部分組合,在這些組合當(dāng)中,由于沒有進(jìn)行TC關(guān)系的驗(yàn)證,存在大量假陽性的學(xué)生、課程組合實(shí)際并不存在選課關(guān)系,導(dǎo)致謂詞PA的探索在許多假陽性的Student節(jié)點(diǎn)上進(jìn)行,降低了查詢效率。

    另一方面,圖探索策略中關(guān)系主導(dǎo)的匹配序列在分布式環(huán)境下可能導(dǎo)致中間結(jié)果在計(jì)算節(jié)點(diǎn)間的往復(fù)傳遞。與關(guān)系方法中的join連接不同,join連接是將scan階段所有收集到的中間結(jié)果匯總到同一節(jié)點(diǎn)進(jìn)行連接工作,join階段類似于單機(jī)環(huán)境。圖探索策略由于數(shù)據(jù)的分布存儲(chǔ),不同實(shí)體節(jié)點(diǎn)可能被劃分到不同的計(jì)算節(jié)點(diǎn),如圖11所示。同一實(shí)體節(jié)點(diǎn)在查詢圖中具有的謂詞關(guān)系可能還未完全驗(yàn)證,匹配序列即要求將匹配的中間結(jié)果傳遞到其他節(jié)點(diǎn),進(jìn)行后續(xù)謂詞關(guān)系的驗(yàn)證,而后又再次返回原節(jié)點(diǎn),進(jìn)行剩余謂詞關(guān)系的探索。

    例如,在圖7(a)所示結(jié)構(gòu)中,關(guān)系主導(dǎo)的匹配序列仍為seq=,如果查詢從u1節(jié)點(diǎn)的候選出發(fā),通過謂詞Adv的探索,中間結(jié)果包含由?Student、?FB候選結(jié)果形成的部分組合。而后,各子查詢被發(fā)送到各u2候選結(jié)果所在計(jì)算節(jié)點(diǎn),進(jìn)行后續(xù)TO謂詞探索,由于u1節(jié)點(diǎn)的謂詞PA關(guān)系并未驗(yàn)證,中間結(jié)果需要再次被發(fā)送到u1候選結(jié)果所在計(jì)算節(jié)點(diǎn),造成了額外的網(wǎng)絡(luò)傳輸與查詢延遲。

    由于關(guān)系主導(dǎo)的匹配序列的一系列問題,本文提出了一種結(jié)構(gòu)主導(dǎo)的分布式子圖匹配算法SDSM,基于各部分結(jié)構(gòu)在分布式環(huán)境中的匹配特點(diǎn),利用CPM分解模型進(jìn)行查詢圖的結(jié)構(gòu)分解,以結(jié)構(gòu)信息指導(dǎo)匹配序列,盡可能地縮減查詢的中間結(jié)果數(shù),提高查詢效率。

    在2.2節(jié)與2.3節(jié)中,為了降低中間結(jié)果數(shù)量,制定了以結(jié)構(gòu)為主導(dǎo)的嚴(yán)格的匹配序列,并完成了核心部分節(jié)點(diǎn)結(jié)果的匹配(記為MC)。各中間結(jié)果路徑在核心節(jié)點(diǎn)部分都得到了唯一(各不相同)的路徑綁定,而匹配過程中與核心節(jié)點(diǎn)相連的路徑節(jié)點(diǎn)或者邊際節(jié)點(diǎn)則以候選集的形式保存,如圖13所示。

    圖13 中間結(jié)果綁定

    路徑節(jié)點(diǎn)由于不存在非樹邊,所以無須用到歷史信息剪枝,沒有必要攜帶完整的歷史信息來造成網(wǎng)絡(luò)傳輸?shù)呢?fù)擔(dān)。對于核心節(jié)點(diǎn)遍歷獲得的中間結(jié)果,如果采用文獻(xiàn)[10]中的全部中間結(jié)果獨(dú)立計(jì)算策略,且攜帶完整的歷史信息直到整個(gè)查詢結(jié)束,不僅會(huì)增大網(wǎng)絡(luò)負(fù)擔(dān),同時(shí)也造成了節(jié)點(diǎn)的重復(fù)計(jì)算。

    圖14 不同中間結(jié)果映射到相同的路徑節(jié)點(diǎn)

    SDSM算法通過分割核心節(jié)點(diǎn)匹配與路徑節(jié)點(diǎn)匹配兩個(gè)過程來實(shí)現(xiàn)高并發(fā)的子路徑匹配連接,如算法3所示。各路徑分支以MC中產(chǎn)生的路徑節(jié)點(diǎn)候選作為起始,執(zhí)行一個(gè)個(gè)獨(dú)立的子路徑查詢,路徑匹配過程可以無冗余地并行化執(zhí)行,提高了查詢的并發(fā)度。各路徑匹配結(jié)果MP最終在主機(jī)節(jié)點(diǎn)上執(zhí)行輕量級(jí)的連接形成最終匹配結(jié)果M。

    算法3結(jié)構(gòu)主導(dǎo)的分布式子圖匹配算法SDSM

    輸入:查詢圖Q,索引Idx。

    輸出:SPARQL查詢匹配結(jié)果M。

    master

    1.無向查詢圖Qud←Q;

    2.(VC,VP,VM)←頂點(diǎn)分解算法Decomposed(Qud);

    3.計(jì)算初始節(jié)點(diǎn)r;

    4.計(jì)算核心結(jié)構(gòu)權(quán)重圖Gw(VC);

    5.sed←MatchingOrder(VC,r,Gw(VC));

    6.sendseqto all Slave;

    7.匹配結(jié)果集M←?;

    8.receiveMc、Mpfrom slave;

    9.for each核心節(jié)點(diǎn)綁定Mcdo

    10.for each路徑節(jié)點(diǎn)綁定Mpdo

    11.M←M∪{MC×MP};

    12.展開M中邊際節(jié)點(diǎn)VM的笛卡爾積部分;

    13.returnM;

    Slave

    14.receiveseqfrom master;

    15.Mc←MatchCoreEdge(seq,Idx);

    16.sendMcto master;

    17.for each路徑節(jié)點(diǎn)候選ui.c∈Mc.set(VP) do

    18.If has visited do

    19.continue;

    20.else

    21.MP←MatchPathEdge(ui.c,Idx)

    22.sendMPto master.

    首先,算法將查詢圖轉(zhuǎn)化為無向查詢圖Qud,并依據(jù)結(jié)構(gòu)對節(jié)點(diǎn)進(jìn)行分解。在Decompose(Qud)操作中,首先將度數(shù)為1的節(jié)點(diǎn)全部加入VM并從Qud中刪除;然后迭代地將新生成的度數(shù)為1的節(jié)點(diǎn)加入VP集合并去除,直到?jīng)]有新的度數(shù)為1的節(jié)點(diǎn)生成;VC即為剩余節(jié)點(diǎn)。算法3-6行依據(jù)2.2節(jié)的相關(guān)討論及算法1進(jìn)行計(jì)算,隨后將查詢計(jì)劃seq發(fā)送給所有計(jì)算節(jié)點(diǎn)。算法14-22行中,依據(jù)2.3節(jié)及本節(jié)相關(guān)討論,在各計(jì)算節(jié)點(diǎn)依照查詢結(jié)構(gòu)執(zhí)行不同匹配策略,最終得到核心匹配結(jié)果Mc、路徑匹配結(jié)果MP并返回給主機(jī)節(jié)點(diǎn)。算法8-13行中,主機(jī)節(jié)點(diǎn)對匹配的中間結(jié)果執(zhí)行輕量級(jí)的join連接,并展開相應(yīng)笛卡爾乘積結(jié)果,返回最終答案集M。

    3 實(shí) 驗(yàn)

    3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

    本文所有實(shí)驗(yàn)均在包括6個(gè)相同計(jì)算節(jié)點(diǎn)的分布式集群上進(jìn)行,每個(gè)計(jì)算節(jié)點(diǎn)采用Intel(R) Core(TM) i7-7700@3.60 GHz八核處理器,物理內(nèi)存為16 GB,硬盤大小為1 TB。節(jié)點(diǎn)間通信使用1 000 Mbit/s以太網(wǎng)。

    實(shí)驗(yàn)分別使用了合成數(shù)據(jù)集LUBM(Lehigh University BenchMark)[26]的4個(gè)生成規(guī)模和真實(shí)數(shù)據(jù)集YAGO2(Yet Another Great Ontology 2)[27]。相關(guān)信息如表1所示,其中#T、#S、#O、#P分別表示三元組數(shù)、主語節(jié)點(diǎn)數(shù)、賓語節(jié)點(diǎn)數(shù)以及不同謂詞數(shù)目。

    合成數(shù)據(jù)集LUBM是由利哈伊大學(xué)開發(fā)的,關(guān)于大學(xué)本體的一種標(biāo)準(zhǔn)且系統(tǒng)的語義Web存儲(chǔ)庫評價(jià)基準(zhǔn)。該基準(zhǔn)旨在評估單個(gè)現(xiàn)實(shí)本體在大型數(shù)據(jù)集上的擴(kuò)展查詢。本文使用數(shù)據(jù)生成器UBA1.7生成了4個(gè)不同規(guī)模的數(shù)據(jù)集,以便進(jìn)行可擴(kuò)展性測試。

    YAGO2是一個(gè)鏈接數(shù)據(jù)知識(shí)庫,主要集成了Wikipedia、WordNet和GeoNames三個(gè)來源的數(shù)據(jù),包含1.2億條三元組,擁有超過1 000萬個(gè)實(shí)體(如個(gè)人、組織、城市等)的知識(shí)。

    表1 數(shù)據(jù)集詳細(xì)信息

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

    將SDSM算法的查詢性能與TriAD、Wukong,StarMR做對比,相關(guān)測試代碼及設(shè)置來源于文獻(xiàn)[7-8,10]。首先,比較了LUBM-2560數(shù)據(jù)集在6個(gè)計(jì)算節(jié)點(diǎn)(包括一個(gè)主節(jié)點(diǎn))上的查詢性能。對于查詢,本文使用了Atre等發(fā)表的基準(zhǔn)查詢[15],它被許多分布式RDF系統(tǒng)所使用[9-11,14,25]。

    如圖15所示,在6個(gè)查詢中,SDSM算法比最快的Wukong分別提高了1.4~3.6倍。將實(shí)驗(yàn)分成2組,其中第一組L1、L2、L3(分別對應(yīng)文獻(xiàn)[14]中的Q1、Q3、Q7查詢),特別地,因?yàn)長2的最終結(jié)果為空,源于基準(zhǔn)查詢中某謂詞關(guān)系雖然在數(shù)據(jù)圖中大量存在,但在其所對應(yīng)的實(shí)體上基數(shù)為0。SDSM中基于類型的摘要統(tǒng)計(jì)在制定查詢計(jì)劃時(shí)很容易發(fā)現(xiàn)了這一點(diǎn),而Wukong及TriAD卻需要遍歷大量中間結(jié)果;L1跟L3分別構(gòu)成了較少及較多的最終結(jié)果(約為初始候選三元組的1/65 000及1/1 000),圖探索的方式比基于關(guān)系的模式擁有近1個(gè)數(shù)量級(jí)的速度提升,基于MapReduce的StarMR算法由于其平臺(tái)計(jì)算的局限性,在每個(gè)查詢上都落后于其他算法1~2個(gè)數(shù)量級(jí),SDSM依據(jù)摘要統(tǒng)計(jì)在核心結(jié)構(gòu)上得到了比Wukong更合理的查詢節(jié)點(diǎn)匹配,并依據(jù)非樹邊的優(yōu)先匹配更快地剪枝了中間結(jié)果,所以得到了更大的性能提升。

    圖15 LUBM-2560上不同算法的平均查詢響應(yīng)時(shí)間

    對于第二組更復(fù)雜(擁有較多模式)的查詢L4、L5、L6(分別對文獻(xiàn)[14]中的Q2、Q1、Q7進(jìn)行了擴(kuò)展),L4中的查詢模式具有很低的選擇性,并且由于不存在環(huán)結(jié)構(gòu),極大地降低了借助結(jié)構(gòu)分解及全歷史剪枝策略帶來的剪枝效果,導(dǎo)致圖探索策略與關(guān)系方法TriAD相比性能提升較少,SDSM較Wukong的性能提升來源于推遲笛卡爾乘積部分連接的操作帶來的收益。查詢L5、L6中的環(huán)結(jié)構(gòu)分別具有較少及較多核心結(jié)構(gòu)匹配結(jié)果,但即使是對于具有較多核心結(jié)構(gòu)匹配結(jié)果的查詢,核心結(jié)構(gòu)的剪枝力度仍然是最大的,之后在路徑節(jié)點(diǎn)上無重復(fù)的高速并行驗(yàn)證進(jìn)一步加速了查詢。

    對于YAGO2數(shù)據(jù)集上的查詢,本文從文獻(xiàn)[11-12]收集所需的查詢集,查詢涵蓋了輕量查詢和復(fù)雜查詢。對于YAGO2上的復(fù)雜查詢Y4、Y5、Y6,實(shí)驗(yàn)得到了與LUBM類似的效果,如圖16(b)所示,SDSM算法較其他算法分別提升了1.2~2.5倍。不同的是,對于圖16(a)中的輕量級(jí)查詢Y1、Y2、Y3,查詢只從常量節(jié)點(diǎn)開始進(jìn)行有限的探索,總查詢時(shí)間較短(通常在數(shù)毫秒之內(nèi))。SDSM與Wukong相比在查詢計(jì)劃上的開銷稍高一些,但這依然在可接受的范圍之內(nèi),因?yàn)椴樵兊钠款i通常由那些復(fù)雜查詢引起,針對復(fù)雜查詢SDSM算法的效率更高。

    (a) (b)圖16 YAGO2上不同算法的平均查詢響應(yīng)時(shí)間

    3.3 可擴(kuò)展性測試

    本文從機(jī)器數(shù)和數(shù)據(jù)集大小兩個(gè)方面對算法的可擴(kuò)展性進(jìn)行了評估。

    對于第一組實(shí)驗(yàn),如圖17所示,當(dāng)服務(wù)器數(shù)量從2臺(tái)逐漸增加到6臺(tái)時(shí),查詢L1-L6的查詢時(shí)間均隨著機(jī)器數(shù)量的增多逐漸減少,證明了SDSM算法能夠有效利用分布式系統(tǒng)的并行性查詢。L2由于在查詢計(jì)劃階段就通過摘要統(tǒng)計(jì)得出結(jié)果為空,所以查詢時(shí)間恒定。對于復(fù)雜查詢L4、L5、L6,查詢時(shí)間的遞減幅度略低于L1、L3,因?yàn)楦嗟姆謪^(qū)增加了通過網(wǎng)絡(luò)傳輸?shù)闹虚g數(shù)據(jù)量,但是存儲(chǔ)模型仍然有效地限制了這一開銷。

    (a)

    (b)圖17 SDSM在不同集群節(jié)點(diǎn)數(shù)目上的表現(xiàn)

    對于第二組實(shí)驗(yàn),本文固定服務(wù)器的數(shù)量為6臺(tái),并且生成了不同規(guī)模的LUBM數(shù)據(jù)集來測試算法擴(kuò)展數(shù)據(jù)的能力。如圖18所示,隨著三元組數(shù)目從5.3×106增加到346×106,即使是復(fù)雜查詢,SDSM的查詢時(shí)間仍能保持近乎線性的增長。因?yàn)樗惴ㄍㄟ^對查詢圖的結(jié)構(gòu)分解,預(yù)先攜帶全歷史信息完成了能大幅度剪枝的環(huán)形結(jié)構(gòu)的匹配,并推遲了笛卡爾積部分的計(jì)算;之后通過無冗余的并行路徑節(jié)點(diǎn)的查詢,最終只需要在主機(jī)上進(jìn)行輕量級(jí)的join連接,路徑數(shù)目不會(huì)過于膨脹,具有良好的伸縮性。

    圖18 SDSM算法在不同數(shù)據(jù)集規(guī)模上的表現(xiàn)

    4 結(jié) 語

    本文提出了一種基于圖探索策略的結(jié)構(gòu)主導(dǎo)的分布式子圖匹配優(yōu)化算法SDSM,有效回答了大規(guī)模RDF圖上的分布式SPARQL查詢。SDSM算法依據(jù)結(jié)構(gòu)特征將查詢圖進(jìn)行分解,結(jié)合基于類型的摘要統(tǒng)計(jì)和以節(jié)點(diǎn)為核心的代價(jià)模型,將復(fù)雜的圖探索問題轉(zhuǎn)化為了查詢樹模型。此外,通過分割匹配過程及推遲笛卡爾積操作來進(jìn)行優(yōu)化,進(jìn)一步加速了查詢。在基準(zhǔn)合成數(shù)據(jù)集LUBM和真實(shí)數(shù)據(jù)集YAGO2進(jìn)行了實(shí)驗(yàn),驗(yàn)證了算法的有效性、高效性和可拓展性。

    圖數(shù)據(jù)劃分問題也是一個(gè)經(jīng)典的NP-Complete問題,未來將結(jié)合更多的圖結(jié)構(gòu)和知識(shí)語義信息作為劃分標(biāo)準(zhǔn)來進(jìn)行更細(xì)致的圖劃分算法研究,以便于更好地支持知識(shí)圖譜上查詢的快速執(zhí)行。

    猜你喜歡
    謂詞三元組核心
    基于語義增強(qiáng)雙編碼器的方面情感三元組提取
    軟件工程(2024年12期)2024-12-28 00:00:00
    基于帶噪聲數(shù)據(jù)集的強(qiáng)魯棒性隱含三元組質(zhì)檢算法*
    我是如何拍攝天和核心艙的
    軍事文摘(2022年14期)2022-08-26 08:16:40
    近觀天和核心艙
    軍事文摘(2022年14期)2022-08-26 08:16:22
    你好!我是“天和”核心艙
    軍事文摘(2022年12期)2022-07-13 03:12:18
    被遮蔽的邏輯謂詞
    ——論胡好對邏輯謂詞的誤讀
    黨項(xiàng)語謂詞前綴的分裂式
    西夏研究(2020年2期)2020-06-01 05:19:12
    關(guān)于余撓三元組的periodic-模
    也談“語言是存在的家”——從語言的主詞與謂詞看存在的殊相與共相
    三元組輻射場的建模與仿真
    精品乱码久久久久久99久播| 亚洲色图综合在线观看| 精品福利观看| 男女午夜视频在线观看| 国产欧美亚洲国产| 中文欧美无线码| 久久久久视频综合| 王馨瑶露胸无遮挡在线观看| 成人国产一区最新在线观看| 成人免费观看视频高清| 老鸭窝网址在线观看| 日韩有码中文字幕| 久久青草综合色| av免费在线观看网站| 亚洲国产成人一精品久久久| 伦理电影免费视频| 一夜夜www| 亚洲七黄色美女视频| 亚洲av欧美aⅴ国产| 中文字幕人妻熟女乱码| 日本撒尿小便嘘嘘汇集6| 99热网站在线观看| 丁香六月欧美| 精品亚洲乱码少妇综合久久| 肉色欧美久久久久久久蜜桃| 亚洲精品国产一区二区精华液| 欧美人与性动交α欧美软件| 欧美在线黄色| 日本a在线网址| 亚洲国产av影院在线观看| 中文字幕av电影在线播放| 美女视频免费永久观看网站| 女人久久www免费人成看片| 亚洲色图 男人天堂 中文字幕| 中文字幕最新亚洲高清| 欧美亚洲日本最大视频资源| 19禁男女啪啪无遮挡网站| 69精品国产乱码久久久| 丝袜美足系列| 在线观看一区二区三区激情| 日韩人妻精品一区2区三区| 熟女少妇亚洲综合色aaa.| 久久精品亚洲熟妇少妇任你| 午夜福利一区二区在线看| 欧美精品一区二区大全| 丰满人妻熟妇乱又伦精品不卡| 美女国产高潮福利片在线看| 91麻豆精品激情在线观看国产 | 精品亚洲成a人片在线观看| 国产亚洲欧美在线一区二区| 日韩一卡2卡3卡4卡2021年| 亚洲中文日韩欧美视频| 免费黄频网站在线观看国产| 亚洲av欧美aⅴ国产| 亚洲欧洲日产国产| 999久久久精品免费观看国产| 亚洲成人国产一区在线观看| 精品熟女少妇八av免费久了| 精品久久久精品久久久| 久久狼人影院| 久久亚洲真实| 国产成人av激情在线播放| 757午夜福利合集在线观看| 久久久久久人人人人人| 国产日韩欧美亚洲二区| 男女无遮挡免费网站观看| 肉色欧美久久久久久久蜜桃| 高清在线国产一区| 国产一区二区三区视频了| 捣出白浆h1v1| 国产97色在线日韩免费| 下体分泌物呈黄色| 亚洲第一青青草原| 女警被强在线播放| 午夜福利影视在线免费观看| h视频一区二区三区| 欧美精品一区二区大全| 日本av手机在线免费观看| 国产成人欧美| 香蕉丝袜av| 精品久久蜜臀av无| 免费一级毛片在线播放高清视频 | h视频一区二区三区| 亚洲精品美女久久av网站| 自线自在国产av| 国产精品99久久99久久久不卡| 我要看黄色一级片免费的| 亚洲精品中文字幕在线视频| 成人亚洲精品一区在线观看| 婷婷丁香在线五月| 一区二区三区激情视频| 精品久久久久久久毛片微露脸| 极品人妻少妇av视频| 咕卡用的链子| 日韩 欧美 亚洲 中文字幕| av超薄肉色丝袜交足视频| 法律面前人人平等表现在哪些方面| 欧美日韩精品网址| 黄片小视频在线播放| 老鸭窝网址在线观看| av超薄肉色丝袜交足视频| 亚洲色图av天堂| 精品国产超薄肉色丝袜足j| 欧美成人午夜精品| videos熟女内射| 人人妻人人澡人人爽人人夜夜| 国产色视频综合| aaaaa片日本免费| 黄色怎么调成土黄色| 热re99久久精品国产66热6| a级片在线免费高清观看视频| 18在线观看网站| av又黄又爽大尺度在线免费看| 欧美日韩国产mv在线观看视频| 动漫黄色视频在线观看| 国产一卡二卡三卡精品| av超薄肉色丝袜交足视频| 多毛熟女@视频| 欧美精品亚洲一区二区| 精品视频人人做人人爽| 免费观看av网站的网址| 国产精品秋霞免费鲁丝片| 国产人伦9x9x在线观看| 国产有黄有色有爽视频| 99riav亚洲国产免费| 国产成人啪精品午夜网站| 美女国产高潮福利片在线看| 日韩视频在线欧美| 视频区欧美日本亚洲| 欧美日韩一级在线毛片| 两个人看的免费小视频| 怎么达到女性高潮| 国产精品99久久99久久久不卡| 在线亚洲精品国产二区图片欧美| 国产精品久久久av美女十八| 精品少妇黑人巨大在线播放| 久久人妻福利社区极品人妻图片| 日本av免费视频播放| aaaaa片日本免费| 日日爽夜夜爽网站| 老司机在亚洲福利影院| 精品亚洲乱码少妇综合久久| 性高湖久久久久久久久免费观看| 欧美人与性动交α欧美精品济南到| 久久人妻av系列| 一本综合久久免费| 妹子高潮喷水视频| 新久久久久国产一级毛片| 99在线人妻在线中文字幕 | 国产在线视频一区二区| 麻豆国产av国片精品| 50天的宝宝边吃奶边哭怎么回事| 又紧又爽又黄一区二区| 国产精品影院久久| 成年人免费黄色播放视频| 欧美成狂野欧美在线观看| 狂野欧美激情性xxxx| 国产精品一区二区免费欧美| 国产精品熟女久久久久浪| 久久久国产欧美日韩av| 国产欧美亚洲国产| 两性夫妻黄色片| 久久影院123| 老司机在亚洲福利影院| 无遮挡黄片免费观看| 少妇裸体淫交视频免费看高清 | 成人18禁高潮啪啪吃奶动态图| 777久久人妻少妇嫩草av网站| 精品一品国产午夜福利视频| 欧美在线一区亚洲| 亚洲精品国产一区二区精华液| 一级黄色大片毛片| avwww免费| cao死你这个sao货| 夫妻午夜视频| 老司机在亚洲福利影院| 免费av中文字幕在线| 天堂俺去俺来也www色官网| 人人妻,人人澡人人爽秒播| 久久精品国产a三级三级三级| 欧美黑人精品巨大| 一本一本久久a久久精品综合妖精| 色94色欧美一区二区| 久久中文看片网| 亚洲黑人精品在线| 国产精品欧美亚洲77777| 欧美 日韩 精品 国产| 国产亚洲精品久久久久5区| 91大片在线观看| 成人国产一区最新在线观看| 国产精品偷伦视频观看了| 王馨瑶露胸无遮挡在线观看| 天堂动漫精品| 午夜久久久在线观看| 每晚都被弄得嗷嗷叫到高潮| 视频在线观看一区二区三区| 高清欧美精品videossex| 欧美老熟妇乱子伦牲交| 精品午夜福利视频在线观看一区 | 成在线人永久免费视频| 高潮久久久久久久久久久不卡| 色在线成人网| 超色免费av| 丝袜美足系列| 精品少妇黑人巨大在线播放| 丰满人妻熟妇乱又伦精品不卡| 嫩草影视91久久| 久久亚洲真实| 免费在线观看视频国产中文字幕亚洲| 性高湖久久久久久久久免费观看| 国产高清国产精品国产三级| 亚洲第一av免费看| 日本wwww免费看| 黄色视频在线播放观看不卡| 久久中文字幕人妻熟女| 亚洲精品国产色婷婷电影| av天堂在线播放| 中国美女看黄片| 亚洲午夜理论影院| 欧美黑人欧美精品刺激| 免费av中文字幕在线| av线在线观看网站| 日韩大码丰满熟妇| 9热在线视频观看99| 欧美日韩中文字幕国产精品一区二区三区 | 精品久久蜜臀av无| 人人妻,人人澡人人爽秒播| 18在线观看网站| 丝瓜视频免费看黄片| 中亚洲国语对白在线视频| 久久 成人 亚洲| 国产主播在线观看一区二区| 狂野欧美激情性xxxx| 老司机靠b影院| 天天操日日干夜夜撸| 亚洲精品av麻豆狂野| 久久久精品免费免费高清| 国产一区二区在线观看av| 亚洲精品成人av观看孕妇| 精品国产一区二区三区久久久樱花| 久久热在线av| 少妇被粗大的猛进出69影院| av又黄又爽大尺度在线免费看| 亚洲熟女毛片儿| 免费观看av网站的网址| 99九九在线精品视频| 欧美黄色片欧美黄色片| 欧美一级毛片孕妇| 男女午夜视频在线观看| 久久久精品国产亚洲av高清涩受| 每晚都被弄得嗷嗷叫到高潮| 久久精品亚洲av国产电影网| 一级黄色大片毛片| 啪啪无遮挡十八禁网站| 99国产精品一区二区三区| 国产欧美亚洲国产| 色视频在线一区二区三区| 国产真人三级小视频在线观看| 别揉我奶头~嗯~啊~动态视频| 亚洲欧美精品综合一区二区三区| 高清黄色对白视频在线免费看| 在线观看免费高清a一片| 宅男免费午夜| 国产高清videossex| 少妇精品久久久久久久| 亚洲人成伊人成综合网2020| 狠狠精品人妻久久久久久综合| 色精品久久人妻99蜜桃| 色婷婷久久久亚洲欧美| 俄罗斯特黄特色一大片| 99久久99久久久精品蜜桃| 中文字幕人妻丝袜一区二区| 中文字幕最新亚洲高清| 国产精品久久久人人做人人爽| 亚洲成a人片在线一区二区| 亚洲精品国产区一区二| 丝袜人妻中文字幕| www日本在线高清视频| 在线天堂中文资源库| 欧美精品av麻豆av| 国产精品久久久人人做人人爽| 一本色道久久久久久精品综合| 三上悠亚av全集在线观看| 久久天躁狠狠躁夜夜2o2o| 久久精品亚洲精品国产色婷小说| 成在线人永久免费视频| 色播在线永久视频| 精品少妇黑人巨大在线播放| 91老司机精品| a级片在线免费高清观看视频| 国产亚洲欧美精品永久| 巨乳人妻的诱惑在线观看| 久久这里只有精品19| 亚洲精品在线美女| 啪啪无遮挡十八禁网站| 老熟妇乱子伦视频在线观看| 69av精品久久久久久 | 午夜福利在线观看吧| 免费在线观看视频国产中文字幕亚洲| 丝袜美腿诱惑在线| 王馨瑶露胸无遮挡在线观看| 国产成人精品在线电影| 国产免费视频播放在线视频| 亚洲中文av在线| 久久人妻av系列| 精品人妻在线不人妻| 成年女人毛片免费观看观看9 | 人妻 亚洲 视频| 久久久久国产一级毛片高清牌| 黑人巨大精品欧美一区二区蜜桃| 无人区码免费观看不卡 | 欧美黄色淫秽网站| 国产男靠女视频免费网站| 亚洲人成电影免费在线| 999久久久国产精品视频| 久久午夜亚洲精品久久| 欧美日韩黄片免| 十八禁人妻一区二区| 激情在线观看视频在线高清 | 色综合欧美亚洲国产小说| 久久精品国产a三级三级三级| 久久香蕉激情| 国产欧美日韩一区二区三区在线| 操出白浆在线播放| 纯流量卡能插随身wifi吗| 久久九九热精品免费| 亚洲欧美日韩另类电影网站| 久久天躁狠狠躁夜夜2o2o| 国产精品久久久久久精品电影小说| 中文字幕人妻丝袜制服| 热99国产精品久久久久久7| 国产精品av久久久久免费| 亚洲av片天天在线观看| 国产男女超爽视频在线观看| 中文字幕高清在线视频| 黄色视频不卡| 少妇猛男粗大的猛烈进出视频| 老汉色av国产亚洲站长工具| 啦啦啦中文免费视频观看日本| 亚洲,欧美精品.| 成人18禁在线播放| 午夜福利一区二区在线看| 成人国产av品久久久| 精品一品国产午夜福利视频| 男女免费视频国产| 一级片'在线观看视频| 亚洲精品成人av观看孕妇| 肉色欧美久久久久久久蜜桃| svipshipincom国产片| 精品福利观看| 久久精品91无色码中文字幕| 国产日韩欧美视频二区| 久久九九热精品免费| 久久久精品区二区三区| 亚洲天堂av无毛| 欧美日韩黄片免| 两性夫妻黄色片| 精品一区二区三区视频在线观看免费 | 亚洲精品成人av观看孕妇| a级毛片在线看网站| 欧美日韩av久久| 啪啪无遮挡十八禁网站| 亚洲欧美日韩另类电影网站| 国产精品偷伦视频观看了| 成人特级黄色片久久久久久久 | a级毛片黄视频| 大型av网站在线播放| 五月天丁香电影| 欧美日韩亚洲综合一区二区三区_| 精品少妇内射三级| 免费高清在线观看日韩| 无限看片的www在线观看| 国产男女超爽视频在线观看| 欧美人与性动交α欧美软件| 欧美在线一区亚洲| 侵犯人妻中文字幕一二三四区| 免费看十八禁软件| 久久国产精品影院| 国产精品成人在线| 婷婷成人精品国产| 精品国产乱码久久久久久小说| 狠狠精品人妻久久久久久综合| 国产精品美女特级片免费视频播放器 | 嫁个100分男人电影在线观看| 国产亚洲av高清不卡| 99riav亚洲国产免费| 成人特级黄色片久久久久久久 | 久热爱精品视频在线9| 中国美女看黄片| 麻豆乱淫一区二区| 日本av免费视频播放| 亚洲国产欧美日韩在线播放| 无人区码免费观看不卡 | 多毛熟女@视频| 久久毛片免费看一区二区三区| 成人18禁在线播放| 亚洲久久久国产精品| 亚洲 欧美一区二区三区| 在线天堂中文资源库| 精品高清国产在线一区| 亚洲人成77777在线视频| 日日爽夜夜爽网站| 久久中文字幕人妻熟女| 国产精品国产高清国产av | 亚洲欧洲日产国产| 欧美激情 高清一区二区三区| 91老司机精品| 午夜福利免费观看在线| 午夜福利影视在线免费观看| 天天操日日干夜夜撸| 一二三四在线观看免费中文在| 最新的欧美精品一区二区| 国产亚洲一区二区精品| 女警被强在线播放| tube8黄色片| 久久久国产一区二区| 久热这里只有精品99| 丰满人妻熟妇乱又伦精品不卡| 国产精品免费一区二区三区在线 | 夜夜骑夜夜射夜夜干| 亚洲欧美一区二区三区黑人| 成年版毛片免费区| 成年人黄色毛片网站| 久久久久久久国产电影| 日本撒尿小便嘘嘘汇集6| 亚洲欧美色中文字幕在线| 高清av免费在线| 80岁老熟妇乱子伦牲交| 黄色怎么调成土黄色| 亚洲av日韩精品久久久久久密| 亚洲av片天天在线观看| 亚洲一码二码三码区别大吗| 一边摸一边做爽爽视频免费| 精品国产乱码久久久久久小说| 日本五十路高清| 国产成人欧美在线观看 | 亚洲精品自拍成人| 蜜桃国产av成人99| 亚洲国产av新网站| 久久狼人影院| 天堂8中文在线网| 日韩熟女老妇一区二区性免费视频| 一区二区三区乱码不卡18| 一夜夜www| 一级a爱视频在线免费观看| 国产精品成人在线| 人人妻,人人澡人人爽秒播| 50天的宝宝边吃奶边哭怎么回事| 成年人免费黄色播放视频| netflix在线观看网站| 欧美激情高清一区二区三区| 777久久人妻少妇嫩草av网站| 国产精品偷伦视频观看了| 三上悠亚av全集在线观看| av福利片在线| 丝袜在线中文字幕| 中文字幕另类日韩欧美亚洲嫩草| 亚洲一码二码三码区别大吗| 丁香六月欧美| 亚洲精品国产精品久久久不卡| 国产成人av激情在线播放| 成年动漫av网址| 色婷婷av一区二区三区视频| 亚洲 国产 在线| 亚洲色图 男人天堂 中文字幕| 午夜激情av网站| 女性生殖器流出的白浆| 91老司机精品| 热99久久久久精品小说推荐| 丰满迷人的少妇在线观看| 大香蕉久久网| www日本在线高清视频| 叶爱在线成人免费视频播放| 国产精品电影一区二区三区 | 悠悠久久av| 亚洲熟女精品中文字幕| 老司机深夜福利视频在线观看| 亚洲精品一二三| 国产精品久久电影中文字幕 | 欧美精品亚洲一区二区| 免费高清在线观看日韩| 丰满迷人的少妇在线观看| 国产深夜福利视频在线观看| 一边摸一边抽搐一进一小说 | 欧美变态另类bdsm刘玥| 亚洲色图综合在线观看| 肉色欧美久久久久久久蜜桃| 亚洲熟女毛片儿| 国产精品秋霞免费鲁丝片| 国产又色又爽无遮挡免费看| 黄色a级毛片大全视频| 国产精品自产拍在线观看55亚洲 | 一区二区日韩欧美中文字幕| 日日夜夜操网爽| 18禁美女被吸乳视频| 国产日韩欧美视频二区| 老司机午夜十八禁免费视频| av视频免费观看在线观看| 国精品久久久久久国模美| 18禁美女被吸乳视频| 中文亚洲av片在线观看爽 | 搡老熟女国产l中国老女人| 日韩人妻精品一区2区三区| 久久久久久人人人人人| 欧美一级毛片孕妇| 亚洲精品美女久久久久99蜜臀| 国产亚洲精品一区二区www | 国产精品一区二区免费欧美| 黄色视频,在线免费观看| 老熟妇乱子伦视频在线观看| 精品熟女少妇八av免费久了| 国产不卡一卡二| 免费在线观看日本一区| 最近最新中文字幕大全免费视频| 国产无遮挡羞羞视频在线观看| 亚洲伊人久久精品综合| 久久天堂一区二区三区四区| 精品国产国语对白av| 色精品久久人妻99蜜桃| 丝瓜视频免费看黄片| 夫妻午夜视频| 91成年电影在线观看| 国产精品免费视频内射| 午夜老司机福利片| 久久久精品免费免费高清| 亚洲精品av麻豆狂野| 国产成人精品久久二区二区91| 久久婷婷成人综合色麻豆| 亚洲第一欧美日韩一区二区三区 | 黑人猛操日本美女一级片| 五月开心婷婷网| 老司机在亚洲福利影院| 18禁黄网站禁片午夜丰满| av在线播放免费不卡| 看免费av毛片| 纵有疾风起免费观看全集完整版| 女人被躁到高潮嗷嗷叫费观| 老司机午夜福利在线观看视频 | 黄色丝袜av网址大全| 国产一区二区三区综合在线观看| 色老头精品视频在线观看| 最黄视频免费看| 一区福利在线观看| 午夜福利视频精品| 日韩人妻精品一区2区三区| 自线自在国产av| www.熟女人妻精品国产| 国产av精品麻豆| 建设人人有责人人尽责人人享有的| 国产97色在线日韩免费| 亚洲av美国av| 757午夜福利合集在线观看| 超色免费av| 欧美av亚洲av综合av国产av| 人人澡人人妻人| 国产亚洲精品久久久久5区| 动漫黄色视频在线观看| 欧美一级毛片孕妇| 国产一区二区激情短视频| 国产精品99久久99久久久不卡| 国产成人一区二区三区免费视频网站| 国产欧美日韩一区二区三| 精品久久久精品久久久| 久久午夜亚洲精品久久| 久久狼人影院| 亚洲成人手机| 亚洲av国产av综合av卡| 午夜激情av网站| 无人区码免费观看不卡 | 亚洲成人手机| 日韩大码丰满熟妇| 亚洲国产毛片av蜜桃av| 国产精品电影一区二区三区 | 伦理电影免费视频| 日韩欧美免费精品| 美女视频免费永久观看网站| 国产亚洲午夜精品一区二区久久| 露出奶头的视频| 老熟妇乱子伦视频在线观看| 国产一区二区在线观看av| 日韩欧美三级三区| 欧美激情久久久久久爽电影 | 一区二区日韩欧美中文字幕| 亚洲成人手机| 国产精品成人在线| 日韩 欧美 亚洲 中文字幕| 中文字幕高清在线视频| 一区二区三区精品91| 国产xxxxx性猛交| 2018国产大陆天天弄谢| 久久久国产精品麻豆| 亚洲成人免费电影在线观看| 欧美一级毛片孕妇| videosex国产| 动漫黄色视频在线观看| 欧美另类亚洲清纯唯美| 黑丝袜美女国产一区| 蜜桃国产av成人99| svipshipincom国产片| 香蕉丝袜av| 久久久久久人人人人人| 色尼玛亚洲综合影院| 中文字幕另类日韩欧美亚洲嫩草| 少妇粗大呻吟视频| 正在播放国产对白刺激| 日本a在线网址| 日韩欧美国产一区二区入口| 天堂8中文在线网| 亚洲国产欧美一区二区综合| 三上悠亚av全集在线观看| 老司机午夜福利在线观看视频 | 国产黄色免费在线视频| 蜜桃国产av成人99| 日韩一卡2卡3卡4卡2021年| 考比视频在线观看|