国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

面向RDF圖的多模式匹配方法

2020-07-06 13:34:48孫云浩李逢雨李冠宇邢維康
關(guān)鍵詞:模式圖模式匹配三元組

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

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

1 引言

在語(yǔ)義網(wǎng)中,資源描述框架[1](Resource Description Framework,RDF)是一種基于圖的數(shù)據(jù)模型,用于Web端的信息共享。給定一個(gè)數(shù)據(jù)圖G和一個(gè)模式圖Q,模式匹配(子圖同構(gòu))問(wèn)題是指搜索數(shù)據(jù)圖G 中所有同構(gòu)于模式圖Q 的數(shù)據(jù)子圖。多模式匹配問(wèn)題是對(duì)模式匹配問(wèn)題的一種擴(kuò)展,其主要的挑戰(zhàn)是多個(gè)模式圖之間的并行策略。為了提高匹配執(zhí)行效率:一方面,對(duì)于存在包含關(guān)系的多個(gè)模式圖,需要避免對(duì)公共查詢子圖的重復(fù)計(jì)算;另一方面,在匹配執(zhí)行過(guò)程中,盡量減少候選數(shù)據(jù)子圖的量。因此,本文提出一種面向RDF 圖的快速多模式匹配方法。

模式匹配問(wèn)題是一種子圖同構(gòu)問(wèn)題。子圖同構(gòu)問(wèn)題是一種典型的NP 完全問(wèn)題,隨著數(shù)據(jù)圖規(guī)模的不斷增大,匹配的時(shí)間效率呈指數(shù)級(jí)變化。在面向RDF 圖匹配處理中,大部分的研究者將RDF 數(shù)據(jù)存儲(chǔ)到關(guān)系表中。Hexastore 采用一種基于索引的解決方案,將RDF 數(shù)據(jù)直接存儲(chǔ)在B+樹(shù)[2]。SW-Store 通過(guò)模式集合中的常量標(biāo)簽將RDF數(shù)據(jù)存儲(chǔ)到一系列的垂直分片表中[3],然后,通過(guò)構(gòu)建關(guān)系表的索引快速地定位到需求的表。Jena 和Sesame 是基于圖數(shù)據(jù)庫(kù)的思想[4-5],其抽離出RDF數(shù)據(jù)的概念構(gòu)成屬性表?;陉P(guān)系表的研究者采用了相似的匹配策略。首先,其通過(guò)模式集合的有界標(biāo)簽來(lái)縮減對(duì)數(shù)據(jù)關(guān)系表的搜索空間;其次,過(guò)濾表中不需要的RDF數(shù)據(jù),以便于達(dá)到對(duì)局部結(jié)果的存儲(chǔ),降低匹配處理過(guò)程的執(zhí)行代價(jià);最后,對(duì)局部結(jié)果進(jìn)行連接運(yùn)算,最終形成匹配的子圖集合。然而,由于RDF數(shù)據(jù)的索引構(gòu)建和預(yù)處理會(huì)有大量的時(shí)間消耗,因此,對(duì)于RDF數(shù)據(jù)的匹配處理具有相當(dāng)大的延遲。

面向一般圖的子圖同構(gòu)算法主要分為三類,基于樹(shù)搜索[6-7]、基于約束傳播[8-9]和基于圖索引[10-11]的子圖同構(gòu)算法。其中,基于圖索引的子圖同構(gòu)算法與基于關(guān)系表的模式匹配算法類似,通過(guò)構(gòu)建圖索引,減少搜索空間,快速搜索到模式圖的匹配子圖。然而,這種方法需要對(duì)整個(gè)數(shù)據(jù)集進(jìn)行全存儲(chǔ),從而導(dǎo)致大量的時(shí)間消耗和存儲(chǔ)代價(jià)?;跇?shù)搜索的子圖同構(gòu)算法利用可行性規(guī)則對(duì)一個(gè)樹(shù)型搜索空間中不需要的候選集進(jìn)行裁剪,以達(dá)到快速匹配的目的?;诩s束傳播的子圖同構(gòu)算法是將子圖同構(gòu)問(wèn)題同構(gòu)于約束傳播問(wèn)題,其目的是找尋那些分配到滿足共同約束的變量集中的值。其主要的思想是基于局部約束的傳播特性,節(jié)點(diǎn)或者邊的一致性會(huì)傳播到圖中的其他部分。因此,在圖中只有很少的候選集被保留。

多模式匹配問(wèn)題是對(duì)模式匹配的一種擴(kuò)展,其主要的挑戰(zhàn)是多個(gè)模式圖之間的并行執(zhí)行策略。多模式匹配處理過(guò)程主要包括多模式圖匹配序列優(yōu)化和匹配策略。多模式圖匹配序列優(yōu)化一般通過(guò)計(jì)算多個(gè)模式圖之間的包含關(guān)系構(gòu)建多模式圖的依賴圖或者依賴樹(shù)。文獻(xiàn)[12]通過(guò)計(jì)算多個(gè)模式圖之間的包含關(guān)系,生成最小依賴樹(shù),并利用依賴樹(shù)的執(zhí)行序列進(jìn)行多模式匹配,一定程度上減少了候選集規(guī)模。文獻(xiàn)[13]提出多模式圖的依賴圖構(gòu)建和優(yōu)化方法,其通過(guò)一個(gè)啟發(fā)式算法制定模式圖執(zhí)行序列,減少了冗余計(jì)算以及候選集緩存。多模式圖匹配策略主要的挑戰(zhàn)是候選集的計(jì)算代價(jià)。文獻(xiàn)[14]提出一個(gè)動(dòng)態(tài)解決方法。該方法能夠避免形成冗余候選集,并且可以在形成最大候選集之前到達(dá)結(jié)果集。文獻(xiàn)[15]提出一種最大公共子圖的優(yōu)化算法,通過(guò)代價(jià)模型計(jì)算確保匹配代價(jià)最小。文獻(xiàn)[16]通過(guò)提出的三元節(jié)點(diǎn)標(biāo)簽序列計(jì)算分組因子,從而得到模式包含映射,通過(guò)模式包含映射得到模式執(zhí)行序列。

本文提出一種面向RDF 圖的快速多模式匹配算法。首先,在D-Tree 構(gòu)建算法中加入剪枝策略,通過(guò)剪枝策略使得構(gòu)建的D-Tree最優(yōu)。其次,提出節(jié)點(diǎn)分片表的概念。為了編排多個(gè)模式圖之間的執(zhí)行序列,構(gòu)建了一種多模式圖的依賴樹(shù)。然而,包含關(guān)系是一種單一、抽象的表示,它不足以表示多個(gè)查詢節(jié)點(diǎn)間的交叉關(guān)系。因此,提出了一個(gè)NFT的概念,用來(lái)表示節(jié)點(diǎn)間的執(zhí)行關(guān)系。最后,提出一個(gè)基于D-Tree 和NFT 的多模式匹配算法,通過(guò)遍歷一次RDF 數(shù)據(jù)圖就可以得到多個(gè)模式圖匹配的數(shù)據(jù)子圖。當(dāng)然,本文方法同樣適用其他的所有有標(biāo)簽、無(wú)標(biāo)簽的圖結(jié)構(gòu),對(duì)于無(wú)標(biāo)簽的圖,可以對(duì)其定點(diǎn)和邊進(jìn)行唯一標(biāo)識(shí)。如通過(guò)統(tǒng)一字典編碼技術(shù)對(duì)屬性圖編碼等。

2 依賴樹(shù)和節(jié)點(diǎn)分片表

2.1 問(wèn)題定義

定義1(基本模式圖)一個(gè)基本模式圖p(Vp,Ep,Lp,?p,varp)是一個(gè)有向標(biāo)簽圖,其中Vp表示節(jié)點(diǎn)集;Ep表示有向邊集;是一個(gè)有向函數(shù),表示從u到v的一條有向邊,其中u,v∈Vp;Lp表示邊和節(jié)點(diǎn)標(biāo)簽集;varp表示一個(gè)標(biāo)簽變量集;表示一個(gè)將節(jié)點(diǎn)和邊映射到對(duì)應(yīng)標(biāo)簽的標(biāo)簽函數(shù)。在一個(gè)模式集中,不存在任意一個(gè)模式圖同構(gòu)于模式p,則p為基本圖模式。

定義2(數(shù)據(jù)圖)一個(gè)數(shù)據(jù)圖是一個(gè)有向標(biāo)簽圖,其中Vd表示節(jié)點(diǎn)集;Ed表示多個(gè)有向邊集;是一個(gè)有向函數(shù),表示從u到v的一條有向邊,其中u,v∈Vd;Ld表示邊和節(jié)點(diǎn)標(biāo)簽集;?d:Vd?Ed→Ld表示一個(gè)將節(jié)點(diǎn)和邊映射到對(duì)應(yīng)標(biāo)簽的標(biāo)簽函數(shù)。

基本模式圖與數(shù)據(jù)圖區(qū)別在基本模式圖的標(biāo)簽可以為變量,變量標(biāo)簽指的是常量標(biāo)簽的一個(gè)集合,也可以稱為標(biāo)簽的值域。因此,給定一個(gè)常量標(biāo)簽c和一個(gè)變量標(biāo)簽v,如果c是v值域內(nèi)的一個(gè)常量,那么c∈v。

定義3(子圖同構(gòu))給定一個(gè)基本模式圖p(Vp,Ep,Lp,?p,varp)和一個(gè)數(shù)據(jù)圖當(dāng)且僅當(dāng)存在一個(gè)雙射函數(shù)f:Vp→Vd滿足:

子圖同構(gòu)處理方法是找尋所有滿足子圖同構(gòu)的節(jié)點(diǎn)對(duì)。給定一個(gè)基本模式圖中節(jié)點(diǎn)vp和數(shù)據(jù)圖中的節(jié)點(diǎn)vd,如果f(vp)=vd并且滿足定義3中(1)和(2),那么搜索到的節(jié)點(diǎn)對(duì)為(vp,vd)。多模式匹配問(wèn)題是對(duì)模式匹配的一個(gè)擴(kuò)展,其側(cè)重于多個(gè)模式圖之間的并行執(zhí)行策略。因此,避免多個(gè)模式圖之間的重復(fù)計(jì)算問(wèn)題是本文研究的重點(diǎn)。

定義4(多模式匹配問(wèn)題)給定一個(gè)基本模式圖集和一個(gè)數(shù)據(jù)圖d,m∈N+。給定任意的一個(gè)基本模式圖p∈P,多模式匹配指的是依次地搜索d中同構(gòu)于p所有匹配的數(shù)據(jù)子圖。

圖1 描述的是多個(gè)模式圖以及它們之間的公共子圖。圖(a)表示多個(gè)基本模式圖,圖中符號(hào)分別表示頂點(diǎn)和邊的標(biāo)簽,“?”表示當(dāng)前標(biāo)簽為變量。任意一個(gè)基本模式圖都不同構(gòu)于其他的基本模式圖。圖(b)表示多個(gè)基本模式圖的公共子圖,其中p6為模式圖p1、p2、p4和p5的公共子圖。

圖1 基本模式圖及其公共子圖

2.2 依賴樹(shù)

依賴樹(shù)的構(gòu)建能夠清晰地描繪出多個(gè)基本模式圖之間的依賴關(guān)系。大部分研究者通過(guò)計(jì)算多個(gè)基本模式圖之間的公共查詢子圖,依靠基本模式圖與公共查詢子圖的包含關(guān)系構(gòu)建依賴樹(shù)和依賴圖。然而,并不是所有的公共查詢子圖都要構(gòu)建到最終的依賴樹(shù)或者依賴圖中的,因?yàn)楣膊樵冏訄D可能存在重疊的部分或者多個(gè)公共查詢子圖依賴一個(gè)相同的基本模式圖集。因此,提出一種公共子圖的裁剪策略。

依賴樹(shù)的構(gòu)建過(guò)程主要包括依賴圖的生成和生成樹(shù)的構(gòu)建。依賴圖的生成是通過(guò)計(jì)算多個(gè)基本模式圖之間的公共查詢子圖,依靠基本模式圖與公共查詢子圖的包含關(guān)系構(gòu)建依賴圖,生成樹(shù)的構(gòu)建是通過(guò)代價(jià)評(píng)估模型對(duì)依賴圖的剪枝操作,為了能夠清晰地表述出代價(jià)評(píng)估模式,給出了殘差圖的定義。

定義5(殘差圖)給定兩個(gè)模式圖pa和pb,并且pa子圖同構(gòu)于pb,那么pb相對(duì)于pa的殘差圖為pb-pa,包含pb中除去子圖同構(gòu)于pa部分后剩余部分的節(jié)點(diǎn)和邊。這些頂點(diǎn)和邊被稱之為殘差點(diǎn)和殘差邊。依賴樹(shù)索引構(gòu)建過(guò)程分為以下幾步:

(1)依賴圖生成(算法1,2~9 行),目的是找到模式間的包含關(guān)系。首先采用子圖同構(gòu)算法找尋多個(gè)基本模式圖的子圖同構(gòu)關(guān)系,若存在子圖同構(gòu)關(guān)系,則構(gòu)造它們之間的依賴關(guān)系。若不存在子圖同構(gòu)關(guān)系,則計(jì)算多個(gè)基本模式圖之間的公共查詢子圖,然后構(gòu)造基本模式圖與公共查詢子圖之間的依賴關(guān)系。

圖1 所示的模式圖集構(gòu)建的依賴圖如圖2(a)所示。依賴圖為一個(gè)有向圖,圖中每條邊連接的兩個(gè)節(jié)點(diǎn)間具有子圖同構(gòu)關(guān)系,如p1子圖同構(gòu)于p4。圖(a)中,p6也子圖同構(gòu)于p4,但是由于p6通過(guò)p1連接到p4,因此省略p6指向p4的邊。圖中實(shí)線節(jié)點(diǎn)表示模式集中存在的節(jié)點(diǎn),虛線節(jié)點(diǎn)表示加入到模式集中的最大公共子圖。

圖2 依賴樹(shù)構(gòu)建過(guò)程

算法1 BuildDTree(P,?)

Input:pattern graph setP={p1,p2,…,pn},user specified parameter for VFT building

Output:D-Tree

1.InitialT=?

2.for each petternpiinPdo

3. for each patternpjinPdo

4.if(SubgraphIsomorphism(pi,pj))then

7. end if

8. end for

9.end for

10.CutRedundantEdge(T)

11.ReturnT

依賴圖構(gòu)建時(shí)間復(fù)雜度為O(N2),N為模式圖的個(gè)數(shù)。

(2)代價(jià)評(píng)估模型,目的是對(duì)依賴圖的冗余節(jié)點(diǎn)和邊進(jìn)行裁剪操作。根據(jù)定義5,生成樹(shù)的代價(jià)函數(shù)表示為:

其中,eij為基本模式圖pi到pj的一條有向邊和表示中節(jié)點(diǎn)和邊的數(shù)量。?為人為給定的參數(shù)。通過(guò)公式(1),可以為每條邊賦予一個(gè)代價(jià),表示基于pi的匹配結(jié)果執(zhí)行pj匹配的代價(jià)。為了對(duì)節(jié)點(diǎn)進(jìn)行評(píng)估,本文設(shè)計(jì)了一個(gè)權(quán)重函數(shù),對(duì)虛線節(jié)點(diǎn)代價(jià)評(píng)估。權(quán)重函數(shù)構(gòu)建為:

定義6(可裁剪節(jié)點(diǎn))給定虛線節(jié)點(diǎn)pi,若其滿足以下條件:①;②,則稱其為可裁剪節(jié)點(diǎn)。其中,parent[pj]表示pj的父親節(jié)點(diǎn)。

例1(可裁剪節(jié)點(diǎn)舉例)如圖2 所示,節(jié)點(diǎn)p6有兩個(gè)孩子節(jié)點(diǎn)分別為p1、p2,p1有兩個(gè)父親節(jié)點(diǎn)分別為p6、p7,p2有兩個(gè)父親節(jié)點(diǎn)分別為p6、p8,因此p6滿足定義6 中兩條約束為可裁剪節(jié)點(diǎn),在其同一層次中p7、p8也為可裁剪節(jié)點(diǎn)。

(3)依賴樹(shù)構(gòu)建,目的是為了最小化整體的匹配代價(jià),減少重復(fù)計(jì)算。這一步對(duì)依賴圖進(jìn)行節(jié)點(diǎn)和邊的裁剪,裁剪后的依賴圖稱為依賴樹(shù)。裁剪節(jié)點(diǎn)時(shí),由于虛線節(jié)點(diǎn)不需要結(jié)果集的輸出,因此只對(duì)虛線節(jié)點(diǎn)及其相連的邊進(jìn)行裁剪。由出度為零的節(jié)點(diǎn)出發(fā)向上遍歷,若某個(gè)節(jié)點(diǎn)為可裁剪節(jié)點(diǎn),且同層次(從根節(jié)點(diǎn)向下遍歷路徑長(zhǎng)度相同的節(jié)點(diǎn)為同一層次)上有多個(gè)可裁剪節(jié)點(diǎn)時(shí),比較這些節(jié)點(diǎn)的權(quán)重,將權(quán)重最大的節(jié)點(diǎn)裁剪掉,直到這一層無(wú)可裁剪節(jié)點(diǎn)為止。重復(fù)此裁剪過(guò)程,直到依賴圖中不存在可裁剪節(jié)點(diǎn),則停止裁剪。圖2(a)中可裁剪節(jié)點(diǎn)為p6、p7、p8,設(shè) ?=0.5,則分別為4.5、3.5、5,p8權(quán)重最大,將p8及其相連節(jié)點(diǎn)裁剪,此時(shí)p6、p7不再是可裁剪節(jié)點(diǎn),且同層以及依賴圖都無(wú)可裁剪節(jié)點(diǎn),則停止裁剪,得到圖2(b)。裁剪邊時(shí),使用最小生成樹(shù)算法,對(duì)于每個(gè)節(jié)點(diǎn)只保留代價(jià)最小的入度邊,以此保證每個(gè)節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)。裁剪邊后得到圖2(c)。時(shí)間復(fù)雜度為O(N),N為模式圖的個(gè)數(shù)。

依賴樹(shù)的存儲(chǔ)引入了模式邊表(圖3)的形式。模式邊表(PE 表)分為三列,第一列表示所有依賴樹(shù)中的節(jié)點(diǎn)(基本模式圖或者公共模式圖),第二列表示第一列中節(jié)點(diǎn)的父節(jié)點(diǎn),第三列表示第一列中節(jié)點(diǎn)與第二列中父節(jié)點(diǎn)的殘差邊。

圖3 模式邊表

2.3 節(jié)點(diǎn)分片表

依賴樹(shù)是對(duì)多個(gè)基本模式圖之間依賴關(guān)系的一種描述。這種依賴關(guān)系可以以理解為對(duì)殘差邊的抽象。通過(guò)這些依賴關(guān)系可以有效地制定多個(gè)基本模式圖之間的執(zhí)行序列。然而,很難在這些單一的,抽象的依賴關(guān)系中發(fā)掘出有助于匹配效率的輔助信息。因此,提出了一個(gè)可以細(xì)化、實(shí)例化依賴關(guān)系的節(jié)點(diǎn)分片表。首先,給出了內(nèi)部邊和外部邊的定義。

定義7(內(nèi)部邊和外部邊)由D-Tree根節(jié)點(diǎn)依次向下遍歷,給定兩個(gè)模式圖p1、p2,p1∈D-Tree,p2∈D-Tree且。存在節(jié)點(diǎn),且存在節(jié)點(diǎn),,邊e(u,v)為節(jié)點(diǎn)u、v的內(nèi)部邊,記為i-edge。存在節(jié)點(diǎn),且存在節(jié)點(diǎn)則為節(jié)點(diǎn)u的外部邊,節(jié)點(diǎn)w的內(nèi)部邊,記為o-edge。

NFT由內(nèi)部節(jié)點(diǎn)片表(簡(jiǎn)寫(xiě)為iNFT)和外部節(jié)點(diǎn)分片表(簡(jiǎn)寫(xiě)為oNFT)組成,其中包含內(nèi)部邊的為iNFT和包含外部邊的為oNFT。NFT 包含兩列:節(jié)點(diǎn)和邊。在NFT 每行中,節(jié)點(diǎn)列只存放一個(gè)節(jié)點(diǎn)v,邊列存放與v節(jié)點(diǎn)相連的內(nèi)部或外部邊,因此iNFT和oNFT被形式化為和

NFT 是基于D-Tree 構(gòu)建的(算法2、算法3)。在DTree 中,由于沒(méi)有其他節(jié)點(diǎn)同構(gòu)于根節(jié)點(diǎn),因此根節(jié)點(diǎn)的節(jié)點(diǎn)和邊被直接存入iNFT 中(算法3 的5、6 行)。給定一個(gè)節(jié)點(diǎn)p1(不是根節(jié)點(diǎn)),它的父親節(jié)點(diǎn)p2和一個(gè)節(jié) 點(diǎn)u∈Vp2,存 在 節(jié) 點(diǎn)v∈Vp1,使 得e(u,v)∈Ep1,,則為u的外部邊,v的內(nèi)部邊。u和被存入oNFT(算法3的8、9行),v和e(u,v)被存入iNFT。算法偽代碼如下:

算法2 NFT(P,?)

Input:pattern graph setP={p1,p2,…,pn},user specified parameter for NFT building

Output:NFT={nft1,nft2,…,nftn}

1.Initial NFT=?

2.T=BuildPatternTree(P,?)

3.P← {b|a=root,child[a]}

4.for each patternpinPdo

5.nft←sub-NFT(p,T,NFT)

6. NFT←NFT ∪nft

7.end for

8.return NFT

例2(NFT 構(gòu)建過(guò)程舉例) 圖 2 為 D-Tree 構(gòu)建的構(gòu)建過(guò)程,圖4表示的是NFT表。p9:由于p9為根節(jié)點(diǎn),p9中節(jié)點(diǎn)?B、?D以及邊e4被存入iNFT中。p6:對(duì)于p9中節(jié)點(diǎn) ?B,在p6中存在節(jié)點(diǎn)?E,使得e2={?B,,因此e2為節(jié)點(diǎn)?B的外部邊;對(duì)于p6中節(jié)點(diǎn)?E,在p6中存在節(jié)點(diǎn)?B,使得,因此e2為節(jié)點(diǎn)?E的內(nèi)部邊。

圖4 節(jié)點(diǎn)分片表

3 多模式匹配算法

描述多模式匹配算法前,首先給定基本模式圖與數(shù)據(jù)圖之間的節(jié)點(diǎn)關(guān)系。給定數(shù)據(jù)圖中的任意節(jié)點(diǎn)vd,模式圖中存在節(jié)點(diǎn)vp與vd匹配,則vd是vp的一個(gè)實(shí)例,被表示為節(jié)點(diǎn)對(duì)(vp,vd)。給定數(shù)據(jù)圖的任意兩個(gè)節(jié)點(diǎn),模式圖中存在節(jié)點(diǎn),滿足的一個(gè)實(shí)例,的一個(gè)實(shí)例,且的一個(gè)三元組實(shí)例。

算法3 sub-NFT(P,T,NFT)

Input:pattern graph setP,PatternTreeT,NFT

Output:NFT

1.Initial NFT=?

2.for each patternpinPdo

3. for eachvin patternpdo

4. ifv?NFT then

5.E(v)={e|eu,v,u∈V(v)} is i-edge

6. iNFT (v)←E(v)∪iNFT(v)

7. else

8.E(v)={e|eu,v,u∈V(v)}-iNFT(v) is o-edge

9. oNFT (v)←E(v)∪oNFT(v)

10. end if

11. end for

12. if child[p]≠? then

13.P=child[p]

14. sub-NFT(P,T,NFT)

15. end if

16.end for

17.return NFT

多模式匹配算法基于D-Tree和NFT,多模式匹配結(jié)果是通過(guò)先序遍歷D-Tree 逐步得到的。得到根節(jié)點(diǎn)proot的結(jié)果集分為以下幾步:

(1)給定proot中的一個(gè)固定節(jié)點(diǎn),在數(shù)據(jù)圖中獲得一個(gè)的實(shí)例節(jié)點(diǎn)vd,并且把它做為一個(gè)初始的數(shù)據(jù)節(jié)點(diǎn)。固定節(jié)點(diǎn)是由和D-Tree得到的。若節(jié)點(diǎn)為固定的,當(dāng)且僅當(dāng)固定節(jié)點(diǎn)由函數(shù)確定。

(2)順序遍歷vd的一階鄰居節(jié)點(diǎn)獲得節(jié)點(diǎn)序,并設(shè)置為下一跳遍歷的初始數(shù)據(jù)節(jié)點(diǎn)。下一跳遍歷數(shù)據(jù)圖時(shí),給定一個(gè)初始數(shù)據(jù)節(jié)點(diǎn)和由它獲得的節(jié)點(diǎn),存在節(jié)點(diǎn)vp,滿足是vp的一個(gè)實(shí)例且則被寫(xiě)入p9的結(jié)果集中。若,則被存入臨時(shí)結(jié)果集Temp中。

算法4 Multi-pattern Matching(D,P,?)

Input:pattern graph setP={p1,p2,…,pn} ,Data graph setD={d1,d2,…,dn};user specified parameter for VFT building

Output:matching set ofp

1.Initialize Temp=? ,VFT=? ,set=?

2.VFT,collectionlable=VFT(P,?)

3.for eachdinDdo

4. get any nodev∈basicpattern ind

5. Temp←addnode(v,d,VFT,Temp)

6. While Temp≠? do

7. while Tempinnode≠?do

8. TraverseInnerNode (Temp,NFT)//遍 歷 內(nèi) 部 節(jié)點(diǎn),并存到Temp中

9. end while

10. ifTempinnode≠V(basicpattern) then

11. traverse the next data graph

12. end if

13. basicset←d∪ basicset

14. whileTempoutnode≠?do

15. TraverseOuterNode(Temp,NFT)//遍歷外部節(jié)點(diǎn),并存到Temp中

16. end while

17. ifpiin collectionlable ∈Tempinnodethen

19. end if

21. end while

22.end for

23.return set

(3)執(zhí)行proot匹配,直到?jīng)]有新的三元組實(shí)例被加入到結(jié)果集中。

孩子節(jié)點(diǎn)結(jié)果集獲得過(guò)程不同于根節(jié)點(diǎn),需要通過(guò)父親節(jié)點(diǎn)的結(jié)果集和臨時(shí)結(jié)果集來(lái)獲得,主要分為以下幾步:

(1)將父親節(jié)點(diǎn)的結(jié)果集復(fù)制到孩子節(jié)點(diǎn)中。

(2)給定孩子節(jié)點(diǎn)pchild的一個(gè)固定節(jié)點(diǎn),在數(shù)據(jù)圖中找到的一個(gè)實(shí)例節(jié)點(diǎn)vd,并把它做為臨時(shí)結(jié)果集中的初始節(jié)點(diǎn)。若節(jié)點(diǎn)為固定的,當(dāng)且僅當(dāng)固定節(jié)點(diǎn)由函數(shù)確定。

(3)順序遍歷vd的一階鄰居節(jié)點(diǎn)獲得臨時(shí)結(jié)果集的節(jié)點(diǎn)序,并設(shè)置為下一跳遍歷的初始數(shù)據(jù)節(jié)點(diǎn)。下一跳遍歷臨時(shí)結(jié)果集時(shí),給定一個(gè)初始數(shù)據(jù)節(jié)點(diǎn)和由他獲得的節(jié)點(diǎn),存在模式節(jié)點(diǎn)vp,滿足是vp的一個(gè)實(shí)例且,則被寫(xiě)入pchild的結(jié)果集中。在臨時(shí)結(jié)果集上重復(fù)執(zhí)行一跳遍歷,直到?jīng)]有新的三元組實(shí)例被添加到臨時(shí)結(jié)果集中。

(4)將臨時(shí)結(jié)果集上最終的初始化數(shù)據(jù)節(jié)點(diǎn)做為數(shù)據(jù)圖上的初始數(shù)據(jù)節(jié)點(diǎn),并執(zhí)行(2)、(3)兩步獲得孩子節(jié)點(diǎn)結(jié)果集。

(5)重復(fù)執(zhí)行(1)~(4)直到獲得所有模式的結(jié)果集為止。

圖5 面向RDF圖多模式匹配過(guò)程

例3(面向RDF 圖多模式匹配過(guò)程)多模式匹配過(guò)程如圖5 所示。圖(a)表示一個(gè)待匹配的數(shù)據(jù)圖,圖(b)、(c)表示D-Tree進(jìn)行多模式匹配過(guò)程中結(jié)果集的變化,其中Result表示結(jié)果集,Temp表示臨時(shí)結(jié)果集。

p9:由于p9是D-Tree的根節(jié)點(diǎn),它的匹配過(guò)程只需要借助內(nèi)部表。首先,,從?C、?D中任意選擇一個(gè)節(jié)點(diǎn)做為固定模式節(jié)點(diǎn)。假設(shè)?B為固定模式節(jié)點(diǎn),在數(shù)據(jù)圖中b1為?B的實(shí)例節(jié)點(diǎn),并把b1設(shè)置為一個(gè)(a)的初始數(shù)據(jù)節(jié)點(diǎn)。通過(guò)一跳遍歷b1,三元組實(shí)例被寫(xiě)入p9的結(jié)果集中,三元組實(shí)例被寫(xiě)入臨時(shí)結(jié)果集。之后,順序的得到d1、d2并將它們?cè)O(shè)置為下一次遍歷的初始節(jié)點(diǎn)。通過(guò)一跳遍歷d1、d2,三元組實(shí)例被寫(xiě)入p9的結(jié)果集中,三元組實(shí)例被寫(xiě)入臨時(shí)結(jié)果集中。

p6:p6的匹配過(guò)程需要借助內(nèi)部表和外部表。由于p6為p9的父節(jié)點(diǎn),把p9的結(jié)果復(fù)制到p6的結(jié)果集中。圖5中由于圖片大小問(wèn)題,將不復(fù)制結(jié)果,只顯示新遍歷得到的結(jié)果。首先,由公式得到固定節(jié)點(diǎn)為?B,b1為?B的實(shí)例節(jié)點(diǎn),并把b1設(shè)置為臨時(shí)結(jié)果集的一個(gè)初始數(shù)據(jù)節(jié)點(diǎn)。通過(guò)一跳遍歷b1,三元組實(shí)例被寫(xiě)入p6的結(jié)果集中,之后獲得節(jié)點(diǎn)e1,由于e1在結(jié)果集中不存在,因此將其做為下一次遍歷的初始節(jié)點(diǎn)。由于,三元組實(shí)例被寫(xiě)入p6的結(jié)果集中。至此,p6的結(jié)果集便得到了。其他模式的模式匹配過(guò)程與p6相似。通過(guò)M-PM 算法,通過(guò)遍歷一次數(shù)據(jù)集便可得到所有模式圖的結(jié)果集。

將本文多模式匹配算法分別與基本多模式匹配算法、文獻(xiàn)[12]的多模式匹配算法以及文獻(xiàn)[16]多模式優(yōu)化算法進(jìn)行比較。其中,基本多模式匹配思想是將DTree 中父節(jié)點(diǎn)的匹配結(jié)果集做為其孩子節(jié)點(diǎn)的輸入的局部結(jié)果集,因此,它能夠很好地降低父節(jié)點(diǎn)與孩子節(jié)點(diǎn)之間重疊部分的計(jì)算。假設(shè)模式圖集大小為n,數(shù)據(jù)集數(shù)量(指三元組模式的數(shù)量)為m,基本多模式匹配的時(shí)間復(fù)雜度為。文獻(xiàn)[12]中多模式匹配算法(MPT),分為基本模式匹配和擴(kuò)展模式匹配兩步,每次將基本模式的匹配結(jié)果集作為擴(kuò)展模式匹配的輸入,因此仍然有一部分?jǐn)?shù)據(jù)圖需要多次遍歷,時(shí)間復(fù)雜度為,且其每次都需要對(duì)中間結(jié)果進(jìn)行保存,大大增加了空間復(fù)雜度,其空間復(fù)雜度為。而此多模式匹配算法不需要對(duì)中間結(jié)果進(jìn)行保存。文獻(xiàn)[16]中多查詢優(yōu)化算法(MQO),通過(guò)模式包含映射確定一個(gè)多模式匹配序列,匹配時(shí)多個(gè)父模式的匹配結(jié)果集作為子模式的匹配數(shù)據(jù)集,因此時(shí)間復(fù)雜度為同時(shí)需要對(duì)中間結(jié)果進(jìn)行緩存,空間復(fù)雜度為。本文多模式匹配算法的時(shí)間復(fù)雜度為因此本文的多模式匹配效率高于其他三個(gè)多模式匹配算法。

4 實(shí)驗(yàn)結(jié)果與分析

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

基本模式圖集。在選擇模式集時(shí),基本模式圖之間的殘差圖是一個(gè)重要影響因素。在D-Tree 中,非葉節(jié)點(diǎn)的殘差圖與模式子圖重疊部分相關(guān)聯(lián)。D-Tree 的深度不斷增加,越靠近根節(jié)點(diǎn)的模式圖,匹配執(zhí)行的次數(shù)越多。

數(shù)據(jù)集:實(shí)驗(yàn)中,選擇一個(gè)仿真數(shù)據(jù)集。DBpedia 2015A描述了運(yùn)動(dòng)和運(yùn)動(dòng)事件的相關(guān)信息,它包含20個(gè)三元組模式的30 000多個(gè)RDF三元組實(shí)例。由于現(xiàn)有較大的真實(shí)數(shù)據(jù)集中三元組模式種類較少(如DBpedia、WikiData、YAGO),很難反映模式圖殘差邊數(shù)量對(duì)多模式匹配效率的影響,因此,對(duì)三元組模式圖進(jìn)行了仿真擴(kuò)展,用于提高三元組模式的維度,生成了一個(gè)基于DBpedia 2015A的仿真數(shù)據(jù)集,它包括300個(gè)三元組模式的300萬(wàn)個(gè)RDF三元組實(shí)例。

為了得出多模式匹配與D-Tree深度、寬度以及殘差邊數(shù)量之間的關(guān)系,同時(shí)為了更準(zhǔn)確的進(jìn)行實(shí)驗(yàn),合成的數(shù)據(jù)集要符合現(xiàn)實(shí)世界中觀察到的一般特征,如模式、結(jié)構(gòu)、大小、分布等。在生成仿真數(shù)據(jù)集時(shí),首先采用文獻(xiàn)[17]中的方法對(duì)原始數(shù)據(jù)進(jìn)行一定的擴(kuò)展,為某些實(shí)例引入新的謂詞,增加三元組模式的個(gè)數(shù),同時(shí)刪除某些三元組,這個(gè)過(guò)程生成了更加現(xiàn)實(shí)和復(fù)雜的數(shù)據(jù)集,增加了邊的多樣性,符合現(xiàn)實(shí)世界的現(xiàn)狀和特征。

其次,采用一個(gè)隨機(jī)生成器對(duì)上一步生成的數(shù)據(jù)集進(jìn)行規(guī)模擴(kuò)展。以數(shù)據(jù)圖節(jié)點(diǎn)數(shù)N和最終數(shù)據(jù)集大小S作為輸入,每次隨機(jī)選擇S/N個(gè)節(jié)點(diǎn)作為核心數(shù)據(jù)節(jié)點(diǎn),對(duì)于每個(gè)核心數(shù)據(jù)節(jié)點(diǎn)v,選擇10~15 個(gè)與v距離為5 跳的節(jié)點(diǎn),并且用邊將它們隨機(jī)連接起來(lái),重復(fù)多次,直到達(dá)到需要的數(shù)據(jù)大小。

實(shí)驗(yàn)配置:實(shí)驗(yàn)環(huán)境為Intel Xeon 5118,擁有24 GB RAM。

4.2 實(shí)驗(yàn)分析

在自己生成的仿真數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),分析D-Tree具有不同深度、寬度以及深度改變時(shí)的多模式匹配效率。

圖6 描述具有相同深度不同寬度D-Tree 的執(zhí)行時(shí)間,圖7 描述具有相同寬度不同深度D-Tree 的執(zhí)行時(shí)間。根節(jié)點(diǎn)包含80 個(gè)三元組模式,并且每個(gè)孩子節(jié)點(diǎn)比其父親節(jié)點(diǎn)多10 條邊。隨著深度的增加,本文算法時(shí)間消耗與基本多模式匹配算法、MPT算法、MQO算法相比分別提高約70%、50%、30%的時(shí)間效率。由于子圖同構(gòu)是一個(gè)NP 完全問(wèn)題,其隨著數(shù)據(jù)的規(guī)模不斷增加呈現(xiàn)指數(shù)級(jí)的時(shí)間復(fù)雜度,因此,在圖6 和圖7 中,隨著深度和廣度的增加,三元組模式的數(shù)量也在不斷的增加。從線性的變化趨勢(shì)中,可以發(fā)現(xiàn)其近似于指數(shù)型的變化,然而,由于三元組模式圖的數(shù)量遠(yuǎn)遠(yuǎn)小于數(shù)據(jù)圖數(shù)量,因此,實(shí)驗(yàn)線性的指數(shù)型變化不夠明顯。

圖6 不同寬度D-Tree的執(zhí)行時(shí)間

圖7 不同深度D-Tree的執(zhí)行時(shí)間

從圖6和圖7綜合來(lái)看,當(dāng)寬度和深度相同時(shí),算法執(zhí)行時(shí)間相同,因此算法的執(zhí)行時(shí)間受深度和廣度的影響相似。

采用相同數(shù)量的三元組模式和殘差邊,改變殘差邊在D-Tree中不同深度位置,執(zhí)行時(shí)間如圖8所示。隨著D-Tree深度改變,深度越深,模式間殘差邊越少,本文算法比其他多模式匹配算法波動(dòng)小,更加穩(wěn)定。而其他算法隨著深度的增加,執(zhí)行的時(shí)間消耗呈現(xiàn)增大。因?yàn)椋疃仍礁?,公共部分的重?fù)計(jì)算的次數(shù)越多,然而,其對(duì)本文算法的影響微乎其微。因此,本文算法僅與殘差邊的數(shù)量有關(guān)。

圖8 模式圖深度改變的執(zhí)行時(shí)間

為增加實(shí)驗(yàn)的真實(shí)性和可靠性,在仿真數(shù)據(jù)集Wet-Div 上進(jìn)行對(duì)比實(shí)驗(yàn),如圖9 所示。WatDiv 是一個(gè)關(guān)于電子商務(wù)的合成數(shù)據(jù)集,包括購(gòu)買(mǎi)產(chǎn)品并撰寫(xiě)評(píng)論的用戶,以及提供產(chǎn)品的零售商等。本文采用擴(kuò)展因子為30,生成有300萬(wàn)個(gè)RDF三元組的數(shù)據(jù)集。

圖9 仿真數(shù)據(jù)集WatDiv實(shí)驗(yàn)

為增加實(shí)驗(yàn)的真實(shí)性和可靠性,同樣在真實(shí)數(shù)據(jù)集YAGO上進(jìn)行對(duì)比實(shí)驗(yàn)(如圖10),采用的數(shù)據(jù)集中包含900多萬(wàn)個(gè)三元組模式。

圖10 真實(shí)數(shù)據(jù)集YAGO實(shí)驗(yàn)

由圖9、10 在仿真數(shù)據(jù)集WatDiv 以及真實(shí)數(shù)據(jù)集YAGO上的實(shí)驗(yàn)可以看出,在仿真和真實(shí)數(shù)據(jù)集上本文算法同樣優(yōu)于其他算法,且算法時(shí)間復(fù)雜度只與殘差邊的多少有關(guān),與D-Tree的深度、寬度無(wú)關(guān),當(dāng)深度改變時(shí)本文算法更加穩(wěn)定。

5 結(jié)束語(yǔ)

本文提出了一種面向RDF 圖的多模式匹配方法。為了表示模式間的依賴關(guān)系,減少重復(fù)計(jì)算,它構(gòu)建了樹(shù)形索引結(jié)構(gòu)(依賴樹(shù)),制定了模式間的執(zhí)行序列。同時(shí)利用節(jié)點(diǎn)分片表,表示節(jié)點(diǎn)間的執(zhí)行序列,根據(jù)節(jié)點(diǎn)序和模式序進(jìn)行多模式匹配,進(jìn)一步減少了重復(fù)計(jì)算,而且能在很大程度上提高模式匹配的效率。盡管此種算法很大的優(yōu)點(diǎn),但仍有許多可改進(jìn)之處,故在今后的研究中會(huì)對(duì)此算法進(jìn)行進(jìn)一步的優(yōu)化并增加真實(shí)數(shù)據(jù)的實(shí)驗(yàn)評(píng)估。

猜你喜歡
模式圖模式匹配三元組
基于語(yǔ)義增強(qiáng)雙編碼器的方面情感三元組提取
軟件工程(2024年12期)2024-12-28 00:00:00
基于帶噪聲數(shù)據(jù)集的強(qiáng)魯棒性隱含三元組質(zhì)檢算法*
“雙勾模式圖”的推廣與應(yīng)用
組織學(xué)模式圖繪畫(huà)視頻的制作及其應(yīng)用
基于模式匹配的計(jì)算機(jī)網(wǎng)絡(luò)入侵防御系統(tǒng)
電子制作(2019年13期)2020-01-14 03:15:32
關(guān)于余撓三元組的periodic-模
具有間隙約束的模式匹配的研究進(jìn)展
OIP-IOS運(yùn)作與定價(jià)模式匹配的因素、機(jī)理、機(jī)制問(wèn)題
模式圖及模式圖訓(xùn)練在口腔修復(fù)學(xué)教學(xué)中的應(yīng)用
基于散列函數(shù)的模式匹配算法
托里县| 柞水县| 北碚区| 南丹县| 睢宁县| 河北省| 武夷山市| 阿勒泰市| 兖州市| 甘德县| 资阳市| 崇文区| 军事| 锡林郭勒盟| 沙坪坝区| 呈贡县| 尚义县| 怀仁县| 卓资县| 玉龙| 赤水市| 苍梧县| 渑池县| 岳西县| 宝清县| 高碑店市| 溧阳市| 文化| 永安市| 股票| 合肥市| 陆河县| 历史| 华宁县| 杨浦区| 开阳县| 巴青县| 阳高县| 迁西县| 琼结县| 赫章县|