異構(gòu)信息網(wǎng)上的可達(dá)性查詢

尹 丹 高 宏 鄒兆年 李建中

（哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150001）（yindan630＠163．com）

異構(gòu)信息網(wǎng)上的可達(dá)性查詢

尹 丹 高 宏 鄒兆年 李建中

（哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150001）（yindan630＠163．com）

隨著圖數(shù)據(jù)規(guī)模的爆炸式增長，其形式也越來越復(fù)雜．異構(gòu)信息網(wǎng)可建模成包含多種類型的頂點(diǎn)和多種類型的邊的圖．例如，文獻(xiàn)數(shù)據(jù)庫、在線購物網(wǎng)站等．首次研究異構(gòu)信息網(wǎng)上的可達(dá)性查詢問題．利用不同類型頂點(diǎn)之間的關(guān)系，查詢2個(gè)頂點(diǎn)滿足路徑模式的可達(dá)性，該問題的時(shí)間復(fù)雜度是多項(xiàng)式的．然而在大規(guī)模的網(wǎng)絡(luò)上，每次查詢遍歷一遍網(wǎng)絡(luò)的時(shí)間開銷也是不能容忍的．現(xiàn)有的可達(dá)性查詢問題主要分為2類：k跳可達(dá)性查詢和帶有標(biāo)簽約束的可達(dá)性查詢．但是這2種問題的算法都不能用于解決異構(gòu)信息網(wǎng)上的可達(dá)性查詢問題．因此，為了實(shí)現(xiàn)高效的在線查詢，提出一種新的索引結(jié)構(gòu)，通過路徑模式的分解，預(yù)先計(jì)算部分路徑模式的可達(dá)信息．當(dāng)在線查詢到來時(shí)，在路徑模式的偏序圖上，快速找到索引結(jié)構(gòu)中存在的路徑子模式，高效地計(jì)算查詢結(jié)果．在真實(shí)和人工數(shù)據(jù)集上進(jìn)行了大量實(shí)驗(yàn)，驗(yàn)證了算法的有效性．

異構(gòu)信息網(wǎng)；查詢處理；可達(dá)性；路徑模式；索引

近年來，越來越多的圖數(shù)據(jù)出現(xiàn)，如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、傳感器網(wǎng)絡(luò)和Web圖等．與此同時(shí)，圖數(shù)據(jù)的規(guī)模也呈爆炸式地增長．截止2014年6月，全球最大的社交網(wǎng)絡(luò)Facebook已有超過13億個(gè)用戶．隨著圖數(shù)據(jù)規(guī)模的爆炸式增長，其形式也越來越復(fù)雜．現(xiàn)實(shí)世界中實(shí)體不僅僅是單純的一種類型，很多時(shí)候多種類型的實(shí)體同時(shí)存在一個(gè)網(wǎng)絡(luò)中，同時(shí)，聯(lián)系也不僅僅存在于同一類型的實(shí)體內(nèi)部，在不同類型的實(shí)體之間同樣也存在著關(guān)系．異構(gòu)信息網(wǎng)可以建模成圖模型，其包含多種類型的頂點(diǎn)和多種類型的邊．文獻(xiàn)數(shù)據(jù)庫、在線購物網(wǎng)站、物聯(lián)網(wǎng)等都可以看成是異構(gòu)信息網(wǎng)．在這些網(wǎng)絡(luò)中，頂點(diǎn)類型多種多樣，不同類型頂點(diǎn)之間的連接關(guān)系也不同．

例1．圖1是一個(gè)異構(gòu)信息網(wǎng)的實(shí)例，來自互聯(lián)網(wǎng)電影數(shù)據(jù)IMDb．該網(wǎng)絡(luò)中，共有4種類型頂點(diǎn)，分別是演員（A）、電影（M）、導(dǎo)演（D）和電影公司（S）．其中，共存在4種頂點(diǎn)間關(guān)系，分別是演員與電影之間的參演關(guān)系、導(dǎo)演與電影之間的指導(dǎo)關(guān)系、電影與電影公司之間的投資關(guān)系以及演員之間的合作關(guān)系．例如，Leonardo參演了電影Titanic和Inception，其中Titanic的導(dǎo)演是Cameron，該導(dǎo)演又指導(dǎo)了電影Avatar，同時(shí)，電影Titanic的投資公司是20th Century Fox和Paramount．

Fig．1 IMDb heterogeneous information network．圖1 IMDb異構(gòu)信息網(wǎng)

可達(dá)性查詢是檢驗(yàn)是否存在一條路徑，從一個(gè)頂點(diǎn)到達(dá)另一個(gè)頂點(diǎn)，是圖分析中一個(gè)基本的操作．分析異構(gòu)信息網(wǎng)可以得到的信息遠(yuǎn)遠(yuǎn)大于同構(gòu)信息網(wǎng)．在異構(gòu)信息網(wǎng)上的可達(dá)性查詢可以挖掘現(xiàn)實(shí)世界中大量潛在的有用信息．通過不同類型頂點(diǎn)之間的關(guān)系，挖掘與結(jié)構(gòu)有關(guān)系的信息，進(jìn)而提供有用的內(nèi)在信息給用戶決策．

異構(gòu)信息網(wǎng)上基于路徑可達(dá)性查詢可定義為如下形式：查詢從源頂點(diǎn)s出發(fā)，經(jīng)過路徑P模式，是否可以到達(dá)目標(biāo)頂點(diǎn)t．

例2．異構(gòu)信息網(wǎng)上基于路徑模式的可達(dá)性查詢．

查詢1．查詢Cameron是否指導(dǎo)由Leonardo參演的電影．這個(gè)查詢可以表達(dá)成異構(gòu)信息網(wǎng)上基于路徑的可達(dá)性查詢，源頂點(diǎn)是導(dǎo)演Cameron，目標(biāo)頂點(diǎn)是演員Leonardo，路徑模式是“D→M→A”．

查詢2．查詢Leonardo與Samuel參演的電影是否為同一導(dǎo)演Cameron執(zhí)導(dǎo)．這個(gè)查詢可以表達(dá)成異構(gòu)信息網(wǎng)上基于路徑的可達(dá)性查詢，源頂點(diǎn)是演員Leonardo，目標(biāo)頂點(diǎn)是演員Samuel，路徑模式“A→M→D→M→A”．在原始圖中，Leonardo與Samuel沒有邊，但是二者在路徑模式“A→M→D→M→A”上是可達(dá)的．

查詢3．查詢演員Leonard與Winslet是否參演過同一部電影，此電影是由Warner Bros公司出品．在該查詢中，源頂點(diǎn)是演員Leonardo，目標(biāo)頂點(diǎn)是演員Winslet，路徑模式是“A→M→S→M→A”．在原始圖中，Leonardo與Winslet之間存在邊，然而該查詢中二者是不可達(dá)的，因?yàn)樗麄儧]有合作的電影是Warner Bros出品．

異構(gòu)信息網(wǎng)上的可達(dá)性查詢反映了2個(gè)頂點(diǎn)在給定路徑模式下是否可達(dá)，與原始圖中這2個(gè)頂點(diǎn)之間是否有邊無關(guān)．原始圖中的2個(gè)頂點(diǎn)之間存在邊，在給定路徑模式上不一定可達(dá)．相似地，原始圖中沒有邊的2個(gè)頂點(diǎn)在給定路徑模式可能是可達(dá)的．不同于傳統(tǒng)的可達(dá)性查詢問題中只關(guān)于頂點(diǎn)之間是否存在路徑，異構(gòu)信息網(wǎng)上的可達(dá)性查詢問題可以深入挖掘頂點(diǎn)之間的聯(lián)系，對(duì)于分析和挖掘異構(gòu)信息網(wǎng)絡(luò)有重大意義．因此本文提出了異構(gòu)信息網(wǎng)絡(luò)上基于路徑模式的可達(dá)性查詢問題．

圖上的可達(dá)性查詢問題已經(jīng)有很多的研究成果．但是目前還沒有異構(gòu)信息網(wǎng)上的可達(dá)性查詢的研究．以往的關(guān)于可達(dá)性查詢的研究工作主要集中在傳統(tǒng)的同構(gòu)圖上，這些方法并不能應(yīng)用到異構(gòu)信息網(wǎng)上．同時(shí)以往工作的可達(dá)性查詢大多數(shù)都是建立在有向無環(huán)圖（directed acyclic graph，DAG）上的，而在異構(gòu)信息網(wǎng)上，環(huán)路是經(jīng)常存在的．我們可以通過將異構(gòu)信息網(wǎng)中的強(qiáng)連通組件壓縮成一個(gè)頂點(diǎn)，將異構(gòu)信息網(wǎng)轉(zhuǎn)化成DAG．然而，這就會(huì)丟失不同類型頂點(diǎn)之間的路徑信息，因此我們無法通過傳統(tǒng)的方法將異構(gòu)信息網(wǎng)轉(zhuǎn)化成DAG．這些挑戰(zhàn)都是本文要解決的問題．

本文研究一種新類型的可達(dá)性查詢，在異構(gòu)信息網(wǎng)絡(luò)上，給定源頂點(diǎn)、目標(biāo)頂點(diǎn)以及路徑，查詢從源頂點(diǎn)出發(fā)，經(jīng)過給定路徑模式，是否可以到達(dá)目標(biāo)頂點(diǎn)．

本文的主要貢獻(xiàn)總結(jié)如下：

1）本文首次研究了異構(gòu)信息網(wǎng)上可達(dá)性查詢問題，利用不同類型頂點(diǎn)之間的關(guān)系，查詢2個(gè)頂點(diǎn)間是否滿足路徑的可達(dá)性，該問題的時(shí)間復(fù)雜度是多項(xiàng)式的；

2）隨著網(wǎng)絡(luò)規(guī)模爆炸式的增長，在線查詢中，每個(gè)查詢都遍歷一遍網(wǎng)絡(luò)的時(shí)間開銷是不能容忍的，因此，為了能夠快速響應(yīng)在線查詢，本文提出一種新的索引結(jié)構(gòu)，預(yù)先計(jì)算部分路徑模式的可達(dá)信息，通過路徑模式的分解，共享部分子路徑模式的可達(dá)信息；

3）通過構(gòu)建路徑模式的偏序圖，提出了貪心的路徑模式選擇策略，選擇出部分路徑模式，用于構(gòu)建索引結(jié)構(gòu)，計(jì)算其可達(dá)信息并存儲(chǔ)；

4）提出了高效的在線查詢處理算法，將查詢模式分解成預(yù)計(jì)算的路徑模式，利用其可達(dá)信息，快速地將查詢結(jié)果返回給用戶，提高了在線查詢效率；

5）在真實(shí)和人工數(shù)據(jù)集上進(jìn)行了大量的實(shí)驗(yàn)，驗(yàn)證了算法的有效性．

1 相關(guān)工作

同構(gòu)圖上的可達(dá)性查詢已經(jīng)有很多研究成果［1］，但是現(xiàn)有的算法都不能應(yīng)用到異構(gòu)信息網(wǎng)絡(luò)上．

最短路徑查詢［2－5］只涉及頂點(diǎn)之間的最短路徑，不能區(qū)分路徑經(jīng)過哪類頂點(diǎn)．k跳可達(dá)性查詢［6－11］是計(jì)算頂點(diǎn)之間的最短路徑是否小于等于k，是最短路徑查詢問題的擴(kuò)展．它們都無法用于挖掘異構(gòu)信息網(wǎng)上頂點(diǎn)間豐富的關(guān)系．

帶有標(biāo)簽約束的可達(dá)性查詢［12－14］是計(jì)算2個(gè)頂點(diǎn)之間路徑上的邊的標(biāo)簽集合是否屬于給定的標(biāo)簽集合．本文研究的異構(gòu)信息網(wǎng)上頂點(diǎn)的可達(dá)性要求路徑上標(biāo)簽的順序是預(yù)先規(guī)定的（即路徑模式），因此無法用帶標(biāo)簽約束的可達(dá)性問題解決本文研究的問題．

異構(gòu)信息網(wǎng)上基于路徑模式的可達(dá)性查詢可以看作是特殊的子圖匹配問題［15－17］．然而，子圖匹配問題是NP完全的，算法的代價(jià)高于本文研究的問題，并不適合解決異構(gòu)信息網(wǎng)上的可達(dá)性查詢問題．

現(xiàn)有的異構(gòu)信息網(wǎng)上的研究工作大多數(shù)來自于Sun［18－22］．文獻(xiàn)［18］搜索異構(gòu)信息網(wǎng)中top－k相似對(duì)象，文獻(xiàn)［19］是關(guān)于異構(gòu)信息網(wǎng)絡(luò)中的鏈接預(yù)測(cè)問題的研究，文獻(xiàn)［23］研究了異構(gòu)信息網(wǎng)上基于網(wǎng)頁文本的實(shí)體識(shí)別問題．這些都無法解決異構(gòu)信息網(wǎng)上的可達(dá)性查詢問題．

2 問題描述

定義1．異構(gòu)信息網(wǎng)．異構(gòu)信息網(wǎng)是一個(gè)有向圖G＝（V，E，T，R， ，φ），其中V是頂點(diǎn)集合，E V× V是邊集合，T是頂點(diǎn)類型集合，R是邊類型集合， ：V→T是從頂點(diǎn)集合V到頂點(diǎn)類型集合T的映射函數(shù)，φ：E→R是從邊集合E到邊類型集合R的映射函數(shù)．

圖1是一個(gè)異構(gòu)信息網(wǎng)實(shí)例．現(xiàn)實(shí)世界中還有很多異構(gòu)信息網(wǎng)的實(shí)例，比如商品購物網(wǎng)站、多媒體分享網(wǎng)站等．

定義2．網(wǎng)絡(luò)模式．圖TG＝（T，R）是異構(gòu)信息網(wǎng)G＝（V，E，T，R， ，φ）的模式，其中T是G中的頂點(diǎn)類型，有向邊集R是G中頂點(diǎn)之間的關(guān)系．

定義3．路徑模式．網(wǎng)絡(luò)模式TG＝（T，R），P＝是定義在TG上的路徑，Ti是頂點(diǎn)類型，Ri是從Ti到Ti＋1的關(guān)系．R1R2…Rl－1定義了T1到Tl復(fù)合關(guān)系．

異構(gòu)信息網(wǎng)的網(wǎng)絡(luò)模式給出了在異構(gòu)信息網(wǎng)中的頂點(diǎn)類型和頂點(diǎn)間的關(guān)系．每個(gè)異構(gòu)信息網(wǎng)是其網(wǎng)絡(luò)模式的一個(gè)實(shí)例．如圖2是圖1所示的IMDb網(wǎng)的網(wǎng)絡(luò)模式，圖1是圖2的一個(gè)實(shí)例．

Fig．2 IMDb network schema．圖2 IMDb網(wǎng)絡(luò)模式

Fig．3 Examples of path schema．圖3 路徑模式舉例

定義4．頂點(diǎn)可達(dá)性．異構(gòu)信息網(wǎng)G＝（V，E，T，R， ，φ）， s，t∈V，s是源頂點(diǎn)，t是目標(biāo)頂點(diǎn)，路徑模式P＝T1→T2→…→Tl， （s）＝T1， （t）＝Tl，若存在路徑p是P的實(shí)例，從s出發(fā)經(jīng)路徑p到達(dá)t，定義為s→Pt．

此處我們定義異構(gòu)信息網(wǎng)絡(luò)上可達(dá)性查詢的形式為Q＝（s，t，P），其中s是源頂點(diǎn)，t是目標(biāo)頂點(diǎn)，P是路徑模式．

異構(gòu)信息網(wǎng)上基于路徑模式可達(dá)性查詢（path reachability query，PRQ）的問題定義如下．

輸入：異構(gòu)信息網(wǎng)G＝（V，E，T，R， ，φ），可達(dá)性查詢Q＝（s，t，P），其中路徑模式P＝T1→T2→…→Tl， （s）＝T1， （t）＝Tl；

輸出：s→Pt是否成立，若成立，則輸出s和t之間的所有路徑實(shí)例．

Fig．4 System framework．圖4 系統(tǒng)框架圖

解決PRQ問題最簡(jiǎn)單的方法是深度優(yōu)先或廣度優(yōu)先搜索．從頂點(diǎn)s出發(fā)，搜索T2類型的頂點(diǎn)，a2是s的鄰接頂點(diǎn)，若 （a2）＝T2，且（s，a2）∈E．從a2出發(fā)，搜索T3類型的頂點(diǎn)，計(jì)算a2的鄰接頂點(diǎn)．遞歸此過程，直到訪問完路徑模式P上的所有路徑實(shí)例．若s→Pt，找出s到t的所有滿足路徑模式P的實(shí)例，否則s到t不可達(dá)．

定理1．異構(gòu)信息網(wǎng)上PRQ問題的時(shí)間復(fù)雜度是PTIME．

證明．異構(gòu)信息網(wǎng)上PRQ問題可通過遍歷一遍異構(gòu)信息網(wǎng)中與查詢中路徑模式相關(guān)的頂點(diǎn)和邊即可得到問題的解，因此該問題時(shí)間復(fù)雜度是O（｜V｜＋｜E｜），其中V是頂點(diǎn)集合，E是邊集合，因此PRQ問題的時(shí)間復(fù)雜度是PTIME．證畢．

然而，當(dāng)網(wǎng)絡(luò)的規(guī)模非常大時(shí)，每種類型的頂點(diǎn)數(shù)量達(dá)上百萬甚至更多，邊的個(gè)數(shù)更多，遍歷一遍這些頂點(diǎn)的時(shí)間開銷非常大．這種遍歷方法無法快速地響應(yīng)在線查詢．因此，本文研究如何高效地處理異構(gòu)信息網(wǎng)上的在線可達(dá)性查詢．我們通過構(gòu)建索引，預(yù)先計(jì)算出一部分路徑模式上頂點(diǎn)的可達(dá)性信息，當(dāng)在線查詢到來時(shí)，通過將查詢的路徑模式分解，利用預(yù)先計(jì)算的索引來快速地響應(yīng)查詢，系統(tǒng)框架如圖4所示．下面我們將詳細(xì)介紹算法的實(shí)現(xiàn)過程．

3 索引構(gòu)建

3．1 路徑模式分解

定義6．路徑模式偏序關(guān)系．給定網(wǎng)絡(luò)模式TG＝（T，R），路徑模式P1＝Ti→Ti＋1→…→Tj和路徑模式P2＝T1→…→Ti→…→Tj→…→Tl，其中1≤i≤j，1≤j≤l．那么存在偏序關(guān)系P1P2，我們說P2包含P1或P1包含于P2．

由定義6可知偏序關(guān)系具有傳遞性．

定義7．路徑模式分解．給定異構(gòu)信息網(wǎng)G＝（V，E，T，R， ，φ）上的路徑模式P＝T1→T2→…→Tl，P1，P2，…，Pk是k個(gè)包含于P的路徑模式，滿足P＝P1P2…Pk．其中“”表示路徑模式Pi中最后一個(gè)頂點(diǎn)類型和Pi＋1中第1個(gè)頂點(diǎn)類型間關(guān)系的合成操作．同時(shí)，定義路徑模式P可分解成P1P2…Pk．

通過將路徑模式P分解為其包含的若干個(gè)不相交的子路徑模式，在每個(gè)子路徑模式上計(jì)算所有頂點(diǎn)對(duì)的可達(dá)性．當(dāng)查詢頂點(diǎn)對(duì)s和t之間經(jīng)由路徑模式P的可達(dá)性時(shí)，其中 （s）＝T1， （t）＝Tl．從s出發(fā)，通過連接子路徑模式上關(guān)于s和t的可達(dá)頂點(diǎn)對(duì)，可得到s到t之間關(guān)于模式P的路徑實(shí)例．

例3．圖5給出一個(gè)包含5種類型頂點(diǎn)的異構(gòu)信息網(wǎng)．對(duì)于路徑模式P＝T1→T2→T3→T4→T5，一種分解方法是P1P2，其中P1＝T1→T2，P2＝T3→T4→T5．表1和表2分別給出了路徑模式P1和P2上可達(dá)頂點(diǎn)對(duì)的路徑實(shí)例．當(dāng)查詢?cè)错旤c(diǎn)是1，目標(biāo)頂點(diǎn)是22，路徑模式是P．我們可以利用路徑模式P的分解子模式的可達(dá)性信息，來得到1和22的可達(dá)性．從路徑模式P1的可達(dá)性信息知，頂點(diǎn)1到8可達(dá)，經(jīng)過路徑1→8，從圖5知頂點(diǎn)8與T3類型的14頂點(diǎn)間右邊．由路徑模式P2可達(dá)性信息知14到22可達(dá)，經(jīng)過路徑14→18→22，那么頂點(diǎn)1到22可達(dá)，經(jīng)過路徑1→8→14→18→22．由此可見，通過路徑模式分解，可以利用子路徑模式的可達(dá)性信息計(jì)算查詢結(jié)果，大大減少了在線查詢的計(jì)算量．

Fig．5 An example of heterogeneous information network．圖5 異構(gòu)信息網(wǎng)實(shí)例

Table 1 Reachability of Path Schema 1表1 路徑模式1的可達(dá)信息

Table 2 Reachability of Path Schema 2表2 路徑模式2的可達(dá)信息

通過預(yù)先計(jì)算出一部分子路徑模式的可達(dá)結(jié)果，可減少在線查詢中每個(gè)查詢的計(jì)算量，可大大提高在線的查詢響應(yīng)效率．由于子路徑模式的可達(dá)性信息在不同查詢中可以重復(fù)利用，因此我們可以構(gòu)建少量路徑模式的可達(dá)信息作為索引結(jié)構(gòu)，進(jìn)一步降低在線查詢的響應(yīng)時(shí)間．

3．2 路徑模式選擇

每個(gè)路徑模式都包含多個(gè)子路徑模式，其分解方法也有多種．不同的路徑模式分解后共享部分子路徑模式，這部分子路徑模式的可達(dá)信息只需要在預(yù)計(jì)算時(shí)計(jì)算一遍，當(dāng)查詢到來時(shí)就不需要計(jì)算這部分信息．如果預(yù)先將所有的路徑模式的可達(dá)信息進(jìn)行預(yù)計(jì)算并存儲(chǔ)，可以最快地響應(yīng)查詢．但是，這需要耗費(fèi)指數(shù)級(jí)的存儲(chǔ)空間，顯然是不可行的．因此我們需要選擇出一部分路徑模式進(jìn)行索引的構(gòu)建，使得在線查詢計(jì)算代價(jià)最?。虼俗钚』樵兤骄樵冺憫?yīng)時(shí)間，快速地響應(yīng)在線查詢．下面就詳細(xì)介紹如何選擇這部分子路徑模式進(jìn)行可達(dá)信息計(jì)算．

給定異構(gòu)信息網(wǎng)G＝（V，E，T，R， ，φ），其路徑模式可按長度劃分為l類（假設(shè)G上最長的路徑模式長度為l）：其中Mi（1≤i≤l）表示長度為i的路徑模式集合，｜Mi｜表示Mi中路徑模式的個(gè)數(shù)．

例4．圖6給出一個(gè)網(wǎng)絡(luò)模式，其中有6種類型的頂點(diǎn)，最長路徑模式的長度為4．該網(wǎng)絡(luò)模式的路徑模式如下：

Fig．6 An example of network schema．圖6 網(wǎng)絡(luò)模式實(shí)例

根據(jù)路徑模式之間的偏序關(guān)系，可以得到路徑模式的偏序圖．

例5．圖7是圖6所示的異構(gòu)信息網(wǎng)的路徑模式偏序圖．圖7頂點(diǎn)為異構(gòu)信息網(wǎng)絡(luò)中所有的路徑模式，且路徑模式按照其長度分層．在圖7中，頂點(diǎn)分為5層，分別是M0，M1，M2，M3，M4，其中M0是長度為0的路徑模式，即路徑模式中只含有一個(gè)頂點(diǎn)類型．對(duì)于處于相鄰層的2個(gè)路徑模式P1和P2，若存在偏序關(guān)系P1P2，那么在偏序圖中，存在一條有向邊從P1指向P2．例如P11＝4→1，P21＝4→1→2，存在P11P21，則有一條有向邊從P11指向P21．

Fig．7 Partial order graph of path schemas．圖7 路徑模式偏序圖

構(gòu)建路徑模式的偏序圖大致思想如下：異構(gòu)信息網(wǎng)G和G上的路徑模式集合S，首先將S中的路徑模式按照長度劃分為l＋1層（假設(shè)最長的路徑模式長度為l）M0，M1，…，Ml；將S中的路徑模式作為偏序圖的頂點(diǎn)集合．若相鄰2層的路徑模式存在偏序關(guān)系，那么有一條有向邊從低層頂點(diǎn)指向高層頂點(diǎn)．

下面給出構(gòu)建路徑模式偏序圖ConPOG算法的偽代碼．

算法1．ConPOG算法．

輸入：異構(gòu)信息網(wǎng)G＝（V，E，T，R， ，φ）及G的路徑模式集S；

根據(jù)路徑模式的長度將路徑劃分為l＋1層（假設(shè)最長的路徑模式長度為l），其時(shí)間開銷是路徑模式的個(gè)數(shù)O（｜S｜）（行①）．將路徑模式作為偏序圖的頂點(diǎn)，偏序圖的邊集初始化為空集，時(shí)間復(fù)雜度是線性的O（1）（行②）．計(jì)算偏序圖的邊集，對(duì)于相鄰2層的路徑模式對(duì)P1，P2，P1∈Mi，P2∈Mi＋1，如果有偏序關(guān)系P1P2，那么存在一條有向邊從P1指向P2（行③～⑤）．判斷P1和P2是否存在偏序關(guān)系P1P2的時(shí)間復(fù)雜度是路徑模式P2的長度，其時(shí)間復(fù)雜度為O（l）（行④）．這個(gè)過程最多循環(huán)｜S｜2次，所以時(shí)間復(fù)雜度為O（l｜S｜2）．最后輸出偏序圖（行⑥）．綜上所述，ConPOG算法的時(shí)間復(fù)雜度為O（l｜S｜2）．

預(yù)先計(jì)算并存儲(chǔ)所有路徑模式的可達(dá)信息需要海量的存儲(chǔ)空間，這是不可行的．因此，我們可以預(yù)先計(jì)算部分路徑模式，當(dāng)在線查詢到來時(shí)，通過利用預(yù)計(jì)算的這部分路徑模式上的頂點(diǎn)可達(dá)性信息和查詢中路徑模式的分解，得到查詢結(jié)果．下面，我們就詳細(xì)研究如何從路徑模式偏序圖中選取這部分預(yù)計(jì)算的路徑模式．

假設(shè)異構(gòu)信息網(wǎng)上的可達(dá)性查詢Q＝（s，t，P）中s，t，P都是隨機(jī)選取的，符合均勻分布，那么用戶的查詢所選取的路徑模式是等概率的．從偏序圖中選取k個(gè)路徑模式進(jìn)行預(yù)計(jì)算構(gòu)建索引，使在線查詢的平均響應(yīng)時(shí)間最短，即所有路徑模式的頂點(diǎn)可達(dá)查詢的平均計(jì)算代價(jià)最?。@個(gè)問題可由頂點(diǎn)覆蓋問題規(guī)約過來，是NP完全的．因此本文針對(duì)路徑模式選擇問題給出啟發(fā)式的貪心選擇策略，由于貪心算法的執(zhí)行過程簡(jiǎn)單，可以縮短索引構(gòu)建的時(shí)間，因此貪心策略的選擇是必要的．

由路徑模式的偏序圖可知，出度越大頂點(diǎn)所代表的路徑模式可以被越多的路徑模式所包含，預(yù)先計(jì)算這部分路徑模式，可以被更多的查詢利用預(yù)計(jì)算的可達(dá)信息，因此貪心地選擇這些路徑模式構(gòu)建索引是可行的，能夠大大加快查詢速度．同時(shí)，對(duì)于一個(gè)路徑模式的分解，其分解的子路徑模式個(gè)數(shù)越少，子路徑模式越長，那么計(jì)算的開銷就越?。虼水?dāng)偏序圖中2個(gè)頂點(diǎn)的出度相等時(shí)，應(yīng)優(yōu)先選擇長度長的路徑模式．

首先調(diào)用構(gòu)建偏序圖ConPOG算法生成路徑模式偏序圖，時(shí)間開銷是O（l｜S｜2）（行①）．根據(jù)偏序圖中頂點(diǎn)的出度，將長度大于0的路徑模式降序排序，時(shí)間復(fù)雜度為O（｜S｜）（行②）．當(dāng)2個(gè)路徑模式出度相等時(shí)，長度較長的路徑模式排在前面，時(shí)間復(fù)雜度為O（｜S｜）（行⑤～⑦）．選擇排序列表中前k個(gè)路徑模式T作為要預(yù)計(jì)算可達(dá)性信息的路徑模式（行⑧），需要O（1）時(shí)間．下面，就為每個(gè)T中的路徑模式計(jì)算可達(dá)性信息（行⑨～ 瑐瑦）．對(duì)于T的路徑模式P，初始化G中所有頂點(diǎn)為標(biāo)簽為unfinded，P的可達(dá)信息表RP為空集，時(shí)間開銷為O（｜V｜）（行⑩ 瑏瑡）．對(duì)于P中第1個(gè)頂點(diǎn)類型的任意頂點(diǎn)u，構(gòu)建一棵以u(píng)為根、高度為O（｜P｜）的樹T，用于存放所有u出發(fā)，路徑模式P上的路徑實(shí)例（行 瑏瑢～ 瑐瑦）．首先初始化T為空，把u作為T的根，u頂點(diǎn)標(biāo)記為finded，時(shí)間開銷為常數(shù)O（1）（行 瑏瑣～ 瑏瑥）．對(duì)于P中第2個(gè)頂點(diǎn)類型的任意頂點(diǎn)w，若存在邊（u，w），把w作為u的兒子插入T中，標(biāo)記w為finded，需要時(shí)間為第1個(gè)頂點(diǎn)類型和第2個(gè)頂點(diǎn)類型之間邊集合大小O（E（T1，T2））（行 瑏瑦～ 瑏瑩）．對(duì)于P中相鄰2個(gè)類型頂點(diǎn) w， （w）＝Ti， v， （v）＝Ti＋1，若w的標(biāo)簽為finded（即在樹T中），若存在（w，v）∈E，那么就將v作為w的兒子插入T中，且標(biāo)記v為finded，時(shí)間開銷為O（E（T2，T3）＋E（T3，T4）＋，…，＋E（Tj－1，Tj））（行 瑐瑠～ 瑐瑥）．那么行 瑏瑢～ 瑐瑥時(shí)間開銷為O（E（T1，T2）＋E（T2，T3）＋，…，＋E（Tj－1，Tj））），我們可以寫成O（｜E｜）．最后將T中所有長度為｜P｜的路徑存放到P的可達(dá)信息索引中，其時(shí)間復(fù)雜度為O（｜V｜＋｜E｜）（行 瑐瑦）．那么，行⑨～ 瑐瑦總的時(shí)間代價(jià)為O（k（｜V｜＋｜E｜））．輸出k個(gè)路徑模式的可達(dá)信息索引為常數(shù)時(shí)間（行 瑐瑧 瑐瑨）．因此構(gòu)建索引ConIndex算法的時(shí)間復(fù)雜度是O（k（｜V｜＋｜E｜））．

4 在線可達(dá)性查詢處理

本節(jié)介紹如何利用第3節(jié)構(gòu)建的可達(dá)信息索引快速有效地響應(yīng)在線的PRQ．用戶輸入查詢Q＝（s，t，P），其中s是源頂點(diǎn)，t是目標(biāo)頂點(diǎn)，P是路徑模式，查詢s到t是否存在路徑實(shí)例滿足路徑模式P．若存在，則輸出所有的路徑實(shí)例，不存在則s到t經(jīng)過路徑模式P不可達(dá)．

對(duì)于一個(gè)查詢的路徑模式，需要按照預(yù)計(jì)算的索引結(jié)構(gòu)進(jìn)行分解，連接預(yù)計(jì)算的子路徑模式可達(dá)信息，快速地計(jì)算出s到t的可達(dá)性．下面詳細(xì)描述如何根據(jù)預(yù)計(jì)算的索引結(jié)構(gòu)將路徑模式P分解．模式P有很多分解方法，分解子路徑模式包含的預(yù)計(jì)算路徑模式越多，且分解的子路徑模式越長，合并子路徑模式的操作越少，時(shí)間就越快，在線響應(yīng)時(shí)間就越短．因此，在偏序圖中，我們貪心地選擇P的預(yù)計(jì)算祖先中長度最長的子路徑模式作為其分解子模式，然后從P中去掉這部分子模式，遞歸地進(jìn)行這個(gè)過程，直到P為空．最后將這些預(yù)計(jì)算的路徑模式上起始頂點(diǎn)為s、目標(biāo)頂點(diǎn)為t的路徑實(shí)例根據(jù)原始圖的邊連接起來，就得到查詢結(jié)果．這里，需要說明的是，偏序圖的第0層是長度為0的路徑模式，即原始圖中的頂點(diǎn)類型，根據(jù)預(yù)計(jì)算的路徑模式將P進(jìn)行分解，當(dāng)P包含的子路徑長度大于0的路徑模式不能連接構(gòu)成P，分解的子路徑模式中就需要包含第0層頂點(diǎn)．

搜索查詢中的P是否在索引中存在，耗費(fèi)時(shí)間O（k）（行①）．若存在，直接輸出索引中的源點(diǎn)為s，目標(biāo)頂點(diǎn)為t的路徑實(shí)例，時(shí)間復(fù)雜度為路徑模式P的索引表大小O（｜R｜）（行②～④）．如不存在，執(zhí)行以下過程．首先，在偏序圖上搜索P的預(yù)計(jì)算路徑子模式（行⑤～ 瑏瑦）．初始化變量時(shí)間開銷為O（1）（行⑤～⑦）．路徑模式P所在層數(shù)為第｜P｜層，我們貪心的搜索P最長的路徑子模式，從｜P｜－1層開始搜索是否有P的子模式在索引中，若有模式R滿足RP，那么將R加入P的子模式集合Ps中，從P中去掉關(guān)于R的頂點(diǎn)類型和關(guān)系得到模式W，繼續(xù)搜索W的子路徑模式，直到W為空集，若｜P｜－1層不存在P的子路徑模式，那么向上搜索｜P｜－2層，直到第0層，此過程的時(shí)間復(fù)雜度是O（｜P｜）（行⑧～ 瑏瑦）．將Ps中路徑模式按照其第1個(gè)頂點(diǎn)類型編號(hào)升序排列U1，U2，…，Uk，那么將這k個(gè)路徑模式連接起來就是P．這個(gè)過程需要O（｜P｜）時(shí)間（行 瑏瑧）．對(duì)于U1的可達(dá)信息索引表中，搜索源頂點(diǎn)是s的路徑實(shí)例集合I，若U1長度為0，那么I就是s頂點(diǎn)，其時(shí)間開銷為U1的索引表R大小O（｜R｜）（行 瑏瑨）．從i等于1開始，對(duì)于相鄰的2個(gè)路徑模式Ui和Ui＋1，I中的任意長度為｜Ui｜＝m的路徑實(shí)例p＝（p1，p2，…，pm）若在Ui＋1的可達(dá)信息索引表中存在源頂點(diǎn)是pm的路徑實(shí)例（q1，q2，…，qn）（pm＝q1），則將插入I中，這個(gè)過程的時(shí)間開銷是O（（k－1）｜R｜2）（假設(shè)每個(gè)索引的大小是｜R｜）（行 瑐瑠～ 瑐瑧）．最后將I中目標(biāo)頂點(diǎn)不是t的路徑實(shí)例刪除，并輸出PI，其時(shí)間開銷為O（｜I｜）（行 瑐瑨～ 瑑瑡）．綜上所述，在線查詢處理算法的時(shí)間復(fù)雜度為O（｜P｜）＋O（k｜R｜2）．該算法的時(shí)間開銷與路徑模式長度與索引大小有關(guān)．

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

本節(jié)給出算法在真實(shí)和人工數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果．實(shí)驗(yàn)環(huán)境為Windows PC機(jī)，Intel?Core i5－2400CPU 3．1GHz，4GB內(nèi)存．實(shí)驗(yàn)運(yùn)行編譯環(huán)境是Microsoft Visual Studio 2010，編程用C語言實(shí)現(xiàn)．

5．1 實(shí)驗(yàn)數(shù)據(jù)集

1）DBLP數(shù)據(jù)集

本文用到的數(shù)據(jù)是2008年從DBLP網(wǎng)站下載的數(shù)據(jù)中提取的［18］，并由此構(gòu)建了異構(gòu)信息網(wǎng)，形式如圖8所示．該網(wǎng)絡(luò)包含5種類型頂點(diǎn)：論文（Paper）、作者（Author）、會(huì)議（Conference）、關(guān)鍵詞（Term）和領(lǐng)域（Field）．本文使用4個(gè)領(lǐng)域的相關(guān)主要會(huì)議所發(fā)表的全部論文，這4個(gè)領(lǐng)域分別是：數(shù)據(jù)庫（DB）、數(shù)據(jù)挖掘（DM）、人工智能（IR）和信息檢索（AI），相關(guān)主要會(huì)議分類如表3所示．同時(shí)4種類型的邊存在于該網(wǎng)絡(luò)中，它們是：論文與作者之間的寫作關(guān)系、論文與會(huì)議之間的發(fā)表關(guān)系、論文與關(guān)鍵詞之間的所屬關(guān)系和會(huì)議與領(lǐng)域之間的分類關(guān)系．本文用到的數(shù)據(jù)集包含28 702位作者在他們這20個(gè)會(huì)議上所發(fā)表的全部論文28 569篇．?dāng)?shù)據(jù)集中共含有13 575個(gè)關(guān)鍵詞．在該網(wǎng)絡(luò)中，作者與文章之間存在74 632條邊、論文與會(huì)議之間存在28 569條邊、論文與關(guān)鍵字之間存在229 187條邊以及會(huì)議與領(lǐng)域之間的20條邊．

Fig．8 DBLP heterogeneous information network．圖8 DBLP異構(gòu)信息網(wǎng)

Table 3 Categories of Main Conferences表3 主要會(huì)議領(lǐng)域劃分

2）人工數(shù)據(jù)

為了驗(yàn)證本文提出算法在大規(guī)模、多類型的異構(gòu)信息網(wǎng)上的效率，我們?nèi)斯ず铣蓴?shù)據(jù)來實(shí)驗(yàn)驗(yàn)證．實(shí)驗(yàn)中，我們生成了包含20種不同類型頂點(diǎn)和40種不同類型的邊的隨機(jī)圖．首先加入2種類型頂點(diǎn)，并把這2種類型相連．然后，每次加入一種新類型頂點(diǎn)，并隨機(jī)選擇一種已存在的頂點(diǎn)類型與其相連，直到20種類型頂點(diǎn)都被加入．在20種頂點(diǎn)類型中，隨機(jī)選擇21個(gè)不連接的頂點(diǎn)類型對(duì)，將其連接得到20種頂點(diǎn)類型和40種不同類型的邊．初始化每種頂點(diǎn)類型包含10萬個(gè)頂點(diǎn)，為了保證不同類型頂點(diǎn)之間的連通性，設(shè)定網(wǎng)絡(luò)的密度為｜｜＝2．對(duì)于任｜｜意2個(gè)相連的頂點(diǎn)類型Ti和Tj，隨機(jī)選擇10萬個(gè)頂點(diǎn)對(duì)u，v，u∈Ti，v∈Tj，將邊（u，v）加入到網(wǎng)絡(luò)中．最后得到網(wǎng)絡(luò)共包含200萬個(gè)頂點(diǎn)和400萬條邊．

5．2 DBLP數(shù)據(jù)實(shí)驗(yàn)結(jié)果

我們從索引的構(gòu)建時(shí)間、索引規(guī)模和查詢響應(yīng)時(shí)間3個(gè)方面在DBLP數(shù)據(jù)集上驗(yàn)證算法的效率．在查詢響應(yīng)時(shí)間衡量上采用圖上的深度優(yōu)先搜索DFS算法作為對(duì)比算法，從源頂點(diǎn)出發(fā)，沿著路徑模式上不同類型的頂點(diǎn)進(jìn)行深度優(yōu)先搜索，找出所有源頂點(diǎn)到目標(biāo)頂點(diǎn)的路徑實(shí)例．

1）索引構(gòu)建時(shí)間

圖9（a）給出了索引構(gòu)建時(shí)間的實(shí)驗(yàn)結(jié)果．橫軸是k值，表示預(yù)計(jì)算的路徑模式個(gè)數(shù)；縱軸是索引構(gòu)建的時(shí)間，單位是s．隨著k值的增大，索引構(gòu)建時(shí)間也增多．在實(shí)驗(yàn)中，我們考察當(dāng)k值從3～7的索引構(gòu)建時(shí)間．由圖9（a）可以看出，隨著k值的增加，索引的構(gòu)建時(shí)間也增加．這是顯而易見的，因?yàn)樾枰?jì)算的路徑模式增多．當(dāng)k值從3增加到7時(shí)，索引的構(gòu)建時(shí)間大約從0．1s增長到2．5s．在圖9（a）中可看到，當(dāng)k值從3增加到4，索引的構(gòu)建時(shí)間增加非常少；當(dāng)k值從4增加到5，索引的構(gòu)建時(shí)間突然增加很大．這是因?yàn)閷?shí)驗(yàn)中所用的DBLP異構(gòu)信息網(wǎng)絡(luò)中不同類型頂點(diǎn)的個(gè)數(shù)差異非常大，并且不同類型頂點(diǎn)間的邊數(shù)目差距也很大，從而導(dǎo)致k值增加產(chǎn)生的非線性時(shí)間開銷．

2）索引的規(guī)模

圖9（b）給出在不同k值情況下索引的規(guī)模．橫軸是k值，表示預(yù)計(jì)算的路徑模式個(gè)數(shù)；縱軸是索引規(guī)模，單位是MB．在實(shí)驗(yàn)中，我們考察當(dāng)k值從3～7的索引構(gòu)建時(shí)間．由圖9（b）可以看出，隨著k值的增加，索引的規(guī)模也隨著增長，因?yàn)橛懈嗟穆窂侥Ｊ缴系捻旤c(diǎn)可達(dá)信息需要存儲(chǔ)．當(dāng)k值從3增加到7時(shí)，索引的規(guī)模大約從1．1MB增長到7．6MB．由圖9（b）可以看出當(dāng)k值由3變?yōu)?，索引的構(gòu)建時(shí)間增加非常少．這是因?yàn)樵黾拥穆窂侥Ｊ剿鶎?duì)應(yīng)的頂點(diǎn)個(gè)數(shù)少，因此，當(dāng)k值由3變?yōu)?時(shí)索引的規(guī)模也增加很少．當(dāng)由4增加到5時(shí)，索引的規(guī)模大大增加．

Fig．9 Experimental results on DBLP dataset．圖9 DBLP數(shù)據(jù)實(shí)驗(yàn)結(jié)果

3）查詢效率

我們?cè)贒BLP異構(gòu)信息網(wǎng)絡(luò)上隨機(jī)產(chǎn)生PRQ，考察算法在不同情況下的查詢效率．圖9（c）當(dāng)查詢中路徑模式長度不同時(shí)，算法的查詢響應(yīng)時(shí)間．橫軸｜P｜表示查詢路徑的長度，縱軸表示查詢的平均響應(yīng)時(shí)間，實(shí)線是本文算法的性能，虛線是對(duì)比算法的性能曲線．因?yàn)镈BLP網(wǎng)絡(luò)中路徑長度最長為3，所以我們考察查詢路徑模式的長度分別為1，2，3時(shí)，算法的在線響應(yīng)時(shí)間．實(shí)驗(yàn)中，我們針對(duì)每種路徑長度，分別隨機(jī)產(chǎn)生1 000個(gè)PRQ，本文的算法中索引規(guī)模k取值為5．由圖9（c）我們可以看出，當(dāng)查詢路徑模式的長度｜P｜從1增加到3時(shí)，查詢的響應(yīng)時(shí)間大約從0．28s增加到0．57s．路徑模式的長度對(duì)查詢響應(yīng)的時(shí)間影響不可忽略，因?yàn)槁窂侥Ｊ降姆纸庾幽Ｊ皆龆啵枰喜⒌拈_銷也變大．同時(shí)，本文的算法的在線查詢響應(yīng)時(shí)間明顯小于對(duì)比算法．因?yàn)閷?duì)比算法每次都需要搜索路徑模式上所有頂點(diǎn)類型的頂點(diǎn)，當(dāng)路徑模式從1增加到3時(shí)，對(duì)比算法的時(shí)間開銷增加明顯大于本文算法．因?yàn)槁窂侥Ｊ介L度增加導(dǎo)致DFS的搜索時(shí)間增加，每次查詢的時(shí)間開銷都增加．對(duì)于用戶大量查詢，對(duì)比算法的性能明顯下降．由圖9（c）我們可以看出，當(dāng)路徑模式長度為3時(shí)，本文提出算法的平均響應(yīng)時(shí)間比對(duì)比算法小0．2s．

圖9（d）給出算法在k值不同的情況下查詢平均響應(yīng)時(shí)間，橫軸表示k值，縱軸表示查詢平均響應(yīng)時(shí)間，單位是s．在實(shí)驗(yàn)中，我們隨機(jī)產(chǎn)生1 000個(gè)查詢．由圖9（d）我們可以看出，當(dāng)k值增加時(shí)，查詢響應(yīng)時(shí)間也隨著變短．因?yàn)樗饕邪目蛇_(dá)信息增多，在線查詢可利用的索引信息增多，計(jì)算量減少．當(dāng)k值從3增加到5時(shí)，查詢響應(yīng)時(shí)間下降迅速，當(dāng)k值從5增加到7時(shí)，查詢響應(yīng)時(shí)間下降緩慢．這是因?yàn)楫?dāng)路徑模式的出度相等時(shí)，我們優(yōu)先選擇長度大的路徑模式，較長的路徑模式可以減少查詢的路徑模式的分解個(gè)數(shù)，降低計(jì)算量，而隨后增加的預(yù)計(jì)算路徑模式都是長度較短的，對(duì)于查詢模式的分解貢獻(xiàn)小于長度較長的路徑模式．

我們同時(shí)考察了偏序圖的構(gòu)建時(shí)間．本文構(gòu)建的DBLP異構(gòu)信息網(wǎng)中包含25個(gè)路徑模式，網(wǎng)絡(luò)的偏序圖構(gòu)建時(shí)間非常短，因?yàn)槠渚W(wǎng)絡(luò)的路徑模式個(gè)數(shù)比圖的規(guī)模相比很小，因此構(gòu)建其偏序圖非?？欤?．3 人工數(shù)據(jù)實(shí)驗(yàn)結(jié)果

為了衡量算法的可擴(kuò)展性，我們用人工數(shù)據(jù)考察算法在大規(guī)模網(wǎng)絡(luò)上的執(zhí)行效率．與在DBLP真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)相同，本節(jié)我們從3個(gè)方面衡量算法的性能．

1）索引構(gòu)建時(shí)間

圖10（a）給出了算法在人工數(shù)據(jù)上索引構(gòu)建時(shí)間．在實(shí)驗(yàn)中，我們選取k值從5增加到30且間隔為5的索引構(gòu)建時(shí)間實(shí)驗(yàn)結(jié)果．從圖10（a）可以看出，索引的構(gòu)建時(shí)間隨著k值增大而增加，當(dāng)k＝30時(shí)，索引的構(gòu)建時(shí)間大約為60s．因?yàn)樗饕臉?gòu)建是在查詢之前完成，且只構(gòu)建一次，因此這并不影響查詢的效率．

2）索引規(guī)模

圖10（b）給出算法在人工數(shù)據(jù)上的索引大小結(jié)果．實(shí)驗(yàn)中，選取與索引構(gòu)建時(shí)間相同的k取值對(duì)比．由圖10（b）可以看出，隨著k值的增加，索引的空間也變大，當(dāng)k值增加到30時(shí)，索引的規(guī)模達(dá)到將近50MB．這與大規(guī)模的網(wǎng)絡(luò)相比，還是很小的，且是存儲(chǔ)空間可容忍的．索引的規(guī)模取決于所選擇的路徑模式的長度以及路徑實(shí)例的個(gè)數(shù)，并不是網(wǎng)絡(luò)中所有邊的加和，因此與網(wǎng)絡(luò)中總邊數(shù)沒有直接關(guān)系．且路徑模式長的路徑實(shí)例個(gè)數(shù)一定不大于其子路徑模式上的路徑實(shí)例個(gè)數(shù)．因此真實(shí)數(shù)據(jù)與人工數(shù)據(jù)的索引規(guī)模的比例與原始網(wǎng)絡(luò)的規(guī)模比例沒有直接關(guān)聯(lián)．

Fig．10 Experimental results on synthetic dataset．圖10 人工數(shù)據(jù)實(shí)驗(yàn)結(jié)果

3）查詢效率

在人工數(shù)據(jù)上的隨機(jī)產(chǎn)生可達(dá)性查詢，考察算法的在線查詢響應(yīng)時(shí)間．圖10（c）給出當(dāng)查詢中路徑模式長度不同時(shí)，算法的查詢響應(yīng)時(shí)間．橫軸｜P｜表示查詢模式的長度．實(shí)驗(yàn)中，我們?nèi)值為10，且對(duì)于每種長度的路徑模式，隨機(jī)產(chǎn)生5 000個(gè)PRQ，來考察算法的在線效率．在圖10（c）中，虛線表示對(duì)比算法的性能，實(shí)線是本文提出的算法性能．由圖10（c）我們可以看出，與對(duì)比算法相比，本文的算法可以更快速地響應(yīng)用戶的在線查詢．且當(dāng)查詢的路徑長度增加時(shí)，對(duì)比算法的查詢響應(yīng)時(shí)間增長較快，而本文提出的方法的查詢時(shí)間增加速度較慢．這是因?yàn)楫?dāng)路徑模式增大時(shí)，路徑模式可分解的子路徑模式也變長，這部分子路徑模式的可達(dá)信息預(yù)先存在索引中，在線查詢時(shí)算法可以直接利用這部分信息，因此就大大減少了相應(yīng)的時(shí)間．當(dāng)查詢路徑模式為10時(shí)，對(duì)比算法的平均響應(yīng)時(shí)間達(dá)到了3．6s，而本文的算法僅為2．1s，每個(gè)查詢提高了1．5s，對(duì)于大規(guī)模的在線查詢，這就大大提高了效率．

圖10（d）給出算法在k值5，10，15，20，25，30時(shí)查詢的平均響應(yīng)時(shí)間對(duì)比結(jié)果，實(shí)驗(yàn)中我們隨機(jī)產(chǎn)生5 000個(gè)PRQ，用來考察算法的在線效率．由圖10（d）我們可以看出，當(dāng)k值增加時(shí)，查詢響應(yīng)時(shí)間也隨著變短．當(dāng)k值由5增加到20時(shí)查詢的時(shí)間下降較快，其后趨于平穩(wěn)下降．因?yàn)椴樵兊漠a(chǎn)生是隨機(jī)的，因此索引中較長的路徑模式對(duì)于降低查詢的計(jì)算量貢獻(xiàn)較大．當(dāng)k值為5時(shí)，查詢的平均響應(yīng)時(shí)間為2．8s；當(dāng)k值增加到30時(shí)，查詢的平均響應(yīng)時(shí)間僅僅是0．3s．這對(duì)大規(guī)模網(wǎng)絡(luò)上的在線查詢來說是非常有意義的．

6 結(jié) 論

本文研究了異構(gòu)信息網(wǎng)絡(luò)上的可達(dá)性查詢問題．利用不同類型頂點(diǎn)之間的關(guān)系，查詢2個(gè)頂點(diǎn)間滿足路徑模式的可達(dá)性．提出一種新的索引結(jié)構(gòu)，通過路徑模式的分解，預(yù)先計(jì)算部分路徑模式的可達(dá)信息．當(dāng)查詢到來時(shí)，在路徑模式的偏序圖上，快速找到索引結(jié)構(gòu)中包含的路徑子模式，高效計(jì)算查詢結(jié)果．最后實(shí)驗(yàn)驗(yàn)證了本文提出的算法能夠在大規(guī)模網(wǎng)絡(luò)上高效響應(yīng)用戶在線查詢．異構(gòu)信息網(wǎng)上的可達(dá)性查詢問題可以深入挖掘不同類型頂點(diǎn)之間的聯(lián)系，對(duì)于分析和挖掘異構(gòu)信息網(wǎng)絡(luò)有重大意義．

［1］Fu Lizhen，Meng Xiaofeng．Reachability indexing for largescale graphs：Studies and forecasts［J］．Journal of Computer Research and Development，2015，52（1）：116 129（in Chinese）（富麗貞，孟小峰．大規(guī)模圖數(shù)據(jù)可達(dá)性索引技術(shù)：現(xiàn)狀與展望［J］．計(jì)算機(jī)研究與發(fā)展，2015，52（1）：116 129）

［2］Agrawal R，Borgida A，Jagadish H V．Efficient management of transitive relationships in large data and knowledge bases［C］??Proc of ACM SIGMOD Int Conf on Management of Data．New York：ACM，1989：253 262

［3］Jin R，Xiang Y，Ruan N，et al．3－h(huán)op：A high－compression indexing scheme for reachability query［C］??Proc of ACM SIGMOD Int Conf on Management of Data．New York：ACM，2009：813 826

［4］Jin R，Xiang Y，Ruan N，et al．Efficiently answering reachability queries on very large directed graphs［C］??Proc of ACM SIGMOD Int Conf on Management of Data．New York：ACM，2008：595 608

［5］Wang Haixun，He Hao，Yang Jun，et al．Dual labeling：Answering graph reachability queries in constant time［C］?? Proc of the 22nd Int Conf on Data Engineering．Piscataway，NJ：IEEE，2006：75 75

［6］Cheng J，Shang Z，Cheng H，et al．K－reach：Who is in your small world［J］．Proceedings of the VLDB Endowment，2012，5（11）：1292 1303

［7］Cohen E，Halperin E，Kaplan H，et al．Reachability and distance queries via 2－h(huán)op labels［J］．SIAM Journal on Computing，2003，32（5）：1338 1355

［8］Wei F．TEDI：Efficient shortest path query answering on graphs［C］??Proc of Int Conf on Management of Data．New York：ACM，2010：99 110

［9］Cheng J，Yu J X．On－Line exact shortest distance query processing［C］??Proc of the 12th Int Conf on Extending Database Technology．New York：ACM，2009：481 492

［10］Xiao Y H，Wu W T，Pei J，et al．Efficiently indexing shortest paths by exploiting symmetry in graphs［C］??Proc of the 12th Int Conf on Extending Database Technology．New York：ACM，2009：493 504

［11］Cheng J，Ke Y P，Chu S，et al．Efficient processing of distance queries in large graphs：A vertex cover approach［C］??Proc of Int Conf on Management of Data．New York：ACM，2012：457 468

［12］Jin R，Hong H，Wang H，et al．Computing label－constraint reachability in graph databases［C］??Proc of ACM SIGMOD Int Conf on Management of Data．New York：ACM，2010：123 134

［13］Jin R，Ruan N，Xiang Y，et al．Path－tree：An efficient reachability indexing scheme for large directed graphs［J］．ACM Trans on Database Systems（TODS），2011，36（1）：7：1 7：44

［14］Xu K，Zou L，Yu J X，et al．Answering label－constraint reachability in large graphs［C］??Proc of ACM Int Conf on Information and Knowledge Management．New York：ACM，2011：1595 1600

［15］Cheng J，Yu J X，Ding B，et al．Fast graph pattern matching［C］??Proc of the 24th Int Conf on Data Engineering．Piscataway，NJ：IEEE，2008：913 922

［16］Tong H，F(xiàn)aloutsos C，Gallagher B，et al．Fast best－effort pattern matching in large attributed graphs［C］??Proc of ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining．New York：ACM，2007：737 746

［17］Zou L，Chen L，Tamer M．Distance－join：Pattern match query in a large graph database［J］．Proceedings of the VLDB Endowment，2009，2（1）：886 897

［18］Sun Y，Han J，Yan X，et al．Pathsim：Meta path－based topk similarity search in heterogeneous information networks［J］．Proceedings of the VLDB Endowment，2011，4（11）：992 1003

［19］Sun Y，Barber R，Gupta M，et al．Co－author relationship prediction in heterogeneous bibliographic networks［C］?? Proc of IEEE Int Conf on Advances in Social Networks Analysis and Mining．Piscataway，NJ：IEEE，2011：121 128

［20］Sun Y，Yu Y，Han J．Ranking－based clustering of heterogeneous information networks with star network schema［C］??Proc of ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining．New York：ACM，2009：797 806

［21］Sun Y，Han J，Zhao P，et al．RankClus：Integrating clustering with ranking for heterogeneous information network analysis［C］??Proc of the 12th Int Conf on Extending Database Technology：Advances in Database Technology．New York：ACM，2009：565 576

［22］Sun Y，Norick B，Han J，et al．Integrating meta－path selection with user－guided object clustering in heterogeneous information networks［C］??Proc of ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining．New York：ACM，2012：1348 1356

［23］Shen W，Han J，Wang J．A probabilistic model for linking named entities in Web text wit heterogeneous information networks［C］??Proc of ACM SIGMOD Int Conf on Management of Data．New York：ACM，2014：1199 1210

Yin Dan，born in 1987．PhD candidate．Her research interests include massive data management and graph database．

Gao Hong，born in 1966．Professor，PhD supervisor．Her research interests include massive data management and wireless sensor networks．

Zou Zhaonian，born in 1979．PhD，lecturer．His research interests include massive data management and graph database．

Li Jianzhong，born in 1950．Professor，PhD supervisor．His research interests include massive data management and wireless sensor networks．

Reachability Query in Heterogeneous Information Networks

Yin Dan，Gao Hong，Zou Zhaonian，and Li Jianzhong
（School of Computer Science and Technology，Harbin Institute of Technology，Harbin150001）

With the size of graph data increasing explosively，the form of graph data is much more complicated．Heterogeneous information networks can be modeled as graphs，which contain multiple types of nodes and multiple types of edges，e．g．，bibliographic database，online shopping website and knowledge graphs．Reachability query in heterogeneous information networks is investigated in this paper．By using different types of relationships between nodes，the reachability of nodes is queried while satisfying specific path schema．This problem is polynomial．However，the time costing can t be tolerant by scanning the big network for answering one query．The existing reachability work can be classified into two categories：K－h(huán)op reachability query and label－constraint reachability query．But these techniques can t be used for processing path－based reachability query in heterogeneous information networks．Therefore，in order to respond online queries efficiently，a novel index structure is proposed，which decomposes path schemas and precomputes the reachability of nodes in sub－path schemas．Online query is computed efficiently by decomposing the query path schema and using the reachability of the indexes．A path schema decomposition strategy is developed by searching the partial order graph of path schemas in order to minimize the query time．Experiments on real world and synthetic data demonstrate the effectiveness of algorithms for reachability query in heterogeneous information networks．

heterogeneous information network；query processing；reachability；path schema；index

TP311．1

2015－11－24；

2015－02－28

國家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目（2012CB316200）；國家自然科學(xué)基金重點(diǎn)項(xiàng)目（61033015）；國家自然科學(xué)基金重大項(xiàng)目（61190115，60933001）；國家自然科學(xué)基金面上項(xiàng)目（61173023）

This work was supported by the National Basic Research Program of China（973Program）（2012CB316200），the Key Program of the National Natural Science Foundation of China（61033015），the Major Program of the National Natural Science Foundation of China（61190115，60933001），and the General Program of the National Natural Science Foundation of China（61173023）．