尹 丹 高 宏 鄒兆年 李建中

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

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

尹 丹 高 宏 鄒兆年 李建中

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

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

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

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

例1．圖1是一個異構(gòu)信息網(wǎng)的實例，來自互聯(lián)網(wǎng)電影數(shù)據(jù)IMDb．該網(wǎng)絡(luò)中，共有4種類型頂點，分別是演員（A）、電影（M）、導(dǎo)演（D）和電影公司（S）．其中，共存在4種頂點間關(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，同時，電影Titanic的投資公司是20th Century Fox和Paramount．

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

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

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

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

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

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

查詢3．查詢演員Leonard與Winslet是否參演過同一部電影，此電影是由Warner Bros公司出品．在該查詢中，源頂點是演員Leonardo，目標頂點是演員Winslet，路徑模式是“A→M→S→M→A”．在原始圖中，Leonardo與Winslet之間存在邊，然而該查詢中二者是不可達的，因為他們沒有合作的電影是Warner Bros出品．

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

2 問題描述

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

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

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

定義3．路徑模式．網(wǎng)絡(luò)模式TG＝（T，R），P＝是定義在TG上的路徑，Ti是頂點類型，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)中的頂點類型和頂點間的關(guān)系．每個異構(gòu)信息網(wǎng)是其網(wǎng)絡(luò)模式的一個實例．如圖2是圖1所示的IMDb網(wǎng)的網(wǎng)絡(luò)模式，圖1是圖2的一個實例．

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

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

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

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

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

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

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

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

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

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

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

然而，當網(wǎng)絡(luò)的規(guī)模非常大時，每種類型的頂點數(shù)量達上百萬甚至更多，邊的個數(shù)更多，遍歷一遍這些頂點的時間開銷非常大．這種遍歷方法無法快速地響應(yīng)在線查詢．因此，本文研究如何高效地處理異構(gòu)信息網(wǎng)上的在線可達性查詢．我們通過構(gòu)建索引，預(yù)先計算出一部分路徑模式上頂點的可達性信息，當在線查詢到來時，通過將查詢的路徑模式分解，利用預(yù)先計算的索引來快速地響應(yīng)查詢，系統(tǒng)框架如圖4所示．下面我們將詳細介紹算法的實現(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個包含于P的路徑模式，滿足P＝P1P2…Pk．其中“”表示路徑模式Pi中最后一個頂點類型和Pi＋1中第1個頂點類型間關(guān)系的合成操作．同時，定義路徑模式P可分解成P1P2…Pk．

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

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

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

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

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

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

3．2 路徑模式選擇

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

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

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

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

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

例5．圖7是圖6所示的異構(gòu)信息網(wǎng)的路徑模式偏序圖．圖7頂點為異構(gòu)信息網(wǎng)絡(luò)中所有的路徑模式，且路徑模式按照其長度分層．在圖7中，頂點分為5層，分別是M0，M1，M2，M3，M4，其中M0是長度為0的路徑模式，即路徑模式中只含有一個頂點類型．對于處于相鄰層的2個路徑模式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中的路徑模式作為偏序圖的頂點集合．若相鄰2層的路徑模式存在偏序關(guān)系，那么有一條有向邊從低層頂點指向高層頂點．

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

算法1．ConPOG算法．

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

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

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

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

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

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

4 在線可達性查詢處理

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

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

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

5 實 驗

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

5．1 實驗數(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種類型頂點：論文（Paper）、作者（Author）、會議（Conference）、關(guān)鍵詞（Term）和領(lǐng)域（Field）．本文使用4個領(lǐng)域的相關(guān)主要會議所發(fā)表的全部論文，這4個領(lǐng)域分別是：數(shù)據(jù)庫（DB）、數(shù)據(jù)挖掘（DM）、人工智能（IR）和信息檢索（AI），相關(guān)主要會議分類如表3所示．同時4種類型的邊存在于該網(wǎng)絡(luò)中，它們是：論文與作者之間的寫作關(guān)系、論文與會議之間的發(fā)表關(guān)系、論文與關(guān)鍵詞之間的所屬關(guān)系和會議與領(lǐng)域之間的分類關(guān)系．本文用到的數(shù)據(jù)集包含28 702位作者在他們這20個會議上所發(fā)表的全部論文28 569篇．數(shù)據(jù)集中共含有13 575個關(guān)鍵詞．在該網(wǎng)絡(luò)中，作者與文章之間存在74 632條邊、論文與會議之間存在28 569條邊、論文與關(guān)鍵字之間存在229 187條邊以及會議與領(lǐng)域之間的20條邊．

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

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

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

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

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

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

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

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

2）索引的規(guī)模

圖9（b）給出在不同k值情況下索引的規(guī)模．橫軸是k值，表示預(yù)計算的路徑模式個數(shù)；縱軸是索引規(guī)模，單位是MB．在實驗中，我們考察當k值從3～7的索引構(gòu)建時間．由圖9（b）可以看出，隨著k值的增加，索引的規(guī)模也隨著增長，因為有更多的路徑模式上的頂點可達信息需要存儲．當k值從3增加到7時，索引的規(guī)模大約從1．1MB增長到7．6MB．由圖9（b）可以看出當k值由3變?yōu)?，索引的構(gòu)建時間增加非常少．這是因為增加的路徑模式所對應(yīng)的頂點個數(shù)少，因此，當k值由3變?yōu)?時索引的規(guī)模也增加很少．當由4增加到5時，索引的規(guī)模大大增加．

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

3）查詢效率

我們在DBLP異構(gòu)信息網(wǎng)絡(luò)上隨機產(chǎn)生PRQ，考察算法在不同情況下的查詢效率．圖9（c）當查詢中路徑模式長度不同時，算法的查詢響應(yīng)時間．橫軸｜P｜表示查詢路徑的長度，縱軸表示查詢的平均響應(yīng)時間，實線是本文算法的性能，虛線是對比算法的性能曲線．因為DBLP網(wǎng)絡(luò)中路徑長度最長為3，所以我們考察查詢路徑模式的長度分別為1，2，3時，算法的在線響應(yīng)時間．實驗中，我們針對每種路徑長度，分別隨機產(chǎn)生1 000個PRQ，本文的算法中索引規(guī)模k取值為5．由圖9（c）我們可以看出，當查詢路徑模式的長度｜P｜從1增加到3時，查詢的響應(yīng)時間大約從0．28s增加到0．57s．路徑模式的長度對查詢響應(yīng)的時間影響不可忽略，因為路徑模式的分解子模式增多，需要合并的開銷也變大．同時，本文的算法的在線查詢響應(yīng)時間明顯小于對比算法．因為對比算法每次都需要搜索路徑模式上所有頂點類型的頂點，當路徑模式從1增加到3時，對比算法的時間開銷增加明顯大于本文算法．因為路徑模式長度增加導(dǎo)致DFS的搜索時間增加，每次查詢的時間開銷都增加．對于用戶大量查詢，對比算法的性能明顯下降．由圖9（c）我們可以看出，當路徑模式長度為3時，本文提出算法的平均響應(yīng)時間比對比算法小0．2s．

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

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

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

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

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

2）索引規(guī)模

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

3）查詢效率

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

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

6 結(jié) 論

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

國家“九七三”重點基礎(chǔ)研究發(fā)展計劃基金項目（2012CB316200）；國家自然科學基金重點項目（61033015）；國家自然科學基金重大項目（61190115，60933001）；國家自然科學基金面上項目（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）．