時間圖查詢在實驗設備管理中應用

黃金晶， 趙 雷

（1.蘇州工業職業技術學院軟件與服務外包學院，江蘇蘇州215104；2.蘇州大學計算機科學與技術學院，江蘇蘇州215006）

0 引 言

實驗室中存放大量的實驗設備和實驗儀器，合理有效的管理這些設備和儀器將大大提高它們的利用率。近年來，隨著實驗設備的不斷更新，這給實驗室管理人員的工作帶來了一定的困難，如何對實驗設備、實驗儀器進行更高效的管理是一個值得深入研究的問題。

本文從圖的角度出發，將實驗設備、管理員、使用者等對象抽象成圖的節點，使用者、管理員與設備之間的關系抽象成圖中節點的邊，使用者在特定時間段里使用了設備，將時間段設置成邊上的時間區間，進而將設備管理抽象成對時間圖數據管理，圖1 所示的為實驗設備時間圖。為了方便描述，將圖1 中的年份設定為2020 年。在圖1 中，從節點“李桐”有箭頭指向“設備A”，箭頭上標注了“使用”，時間為“3 月7 日9：00～9：45”，說明“李桐”在3 月7 日的9：00 ～9：45 使用了“設備A”。當管理員需要了解“李桐”3 月7 日使用了哪些設備的時候，其實就是要執行一個查詢。本文利用了圖匹配技術，從時間圖中匹配出相關的查詢結果，并將其運用于實驗設備的管理中，能夠快速地在眾多對象與設備的關系中，找出所需要的信息。

圖1 設備時間圖

1 相關研究現狀

圖匹配一般分為子圖同構和子圖模擬2 種。子圖同構［1］是一個NP 問題，它要求從數據圖中找到和查詢圖完全一致的子圖，對圖的拓撲結構有嚴格的要求。Ullmann［2］是典型的基于圖結構的匹配方法，GraphGrep［3］是經典的基于路徑查詢的圖匹配算法，GIndex［4］算法是對頻繁子圖建立索引幫助快速的查找子圖。事實上子圖同構往往很難匹配到完全一致的結果，近年來，學者們從不同的角度進行了圖的近似查詢，即子圖模擬［5］，它允許匹配的結果與查詢圖之間存在一定差別，比如SUBDUE［6］和SAPPER［7］等。隨著圖規模的增大，傳統的圖匹配技術不能有效的匹配出結果，文獻［8-10］中是使用了分布式技術進行圖匹配，文獻［11-12］則是利用了top-k技術查詢出符合要求的前k個結果，滿足實際應用。在動態圖匹配研究上，文獻［13-14］中主要采用增量處理技術，對新增數據進行匹配。在時間圖匹配上，文獻［15-16］中研究了有時間限制關系的圖匹配，本文主要研究時間圖上包含時間關系的查詢，將查詢轉換為查詢圖，利用時間圖的匹配找到相關結果，并將其應用于實驗設備的管理中。

2 問題定義

下面給出本文所述問題的相關定義。

定義1時間圖G。給定一個時間圖G ＝｛V，LV，E，LE，TE｝，其中V 是圖中點的集合；LV是點的標簽集合；E 是圖中全部邊的集合；LE是邊上的關系標簽集合；TE為邊上關系存在的時間集合，TE中的每個元素都是一個時間段［ts，te］，ts為起始時間，te為終止時間，若te為“*”表示至今。

定義2查詢圖Q。給定一個查詢圖，其中Q ＝｛V，LV，E，LE，TE｝，V ＝Vl∪Vp是查詢圖中點的集合，Vl是查詢圖中已知的點，Vp是查詢圖中待查的點；LV是點的標簽集合，若LV＝“？”表示對應的V 點為待查詢的點；E是圖中全部邊的集合，LE是邊上的標簽集合，若LE＝“？”表示對應邊上的關系為待查詢的關系；TE為查詢圖中給定的時間集合。

定義3時間匹配。給定一個查詢圖Q中的時間段為［tqs，tqe］，時間圖G 中的時間段為［ts，te］，［ts，te］能形成［tqs，tqe］的匹配需滿足［ts，te］和［tqs，tqe］重合或者部分重合，即符合如下3 種情況之一：

①ts≤tqs≤te≤tqe；②ts≤tqs≤tqe≤te；③tqs≤ts≤tqe≤te。

定義4單元查詢圖QU。QU≤Q，QU只包含2 個點V1和V2、連接這兩個點的邊、邊上的關系和時間段。若Vi＝“？”（i ＝1，2），則Vi為待查詢的點；LE＝ “？”表示連接V1和V2邊上的關系為待查的。

圖2 所示的為單元查詢圖示例。圖2（a）表示在時間圖中查詢3 月7 日9：00 ～11：00 間李桐是否使用過設備A。單元查詢圖中的“？”表示待查的元素，可以是點，也可以是邊上的關系，圖2（b）和2（c）表示單個的節點是未知元素，分別查詢誰在3 月7 日9：00 ～11：00 使用了“設備A”以及“李桐”在3 月7 日9：00 ～11：00 使用了什么設備。圖2（d）表示單個的節點和邊上的關系都是未知元素，即查詢3 月7 日9：00 ～11：00 設備A經歷了哪些操作。圖2（e）表示查詢節點之間的關系，即查詢“李桐”在3 月7 日9：00 ～11：00對“設備A”做了哪些操作。圖2（f）所示的只有關系是已知的，2 個節點的值都是未知的，即查詢3 月7 日9：00 ～11：00 哪些人使用了哪些設備。

圖2 單元查詢圖

定義5單元匹配。單元查詢圖QU在G中的匹配結果稱為單元匹配。對于一個給定的時間圖G，一個單元匹配圖QU，R 是G 的一個子集，令QU的點集為｛V1，V2｝，R的點集為｛U1，U2｝，若R 是Q 的一個單元匹配要滿足：

①LU1＝LV1，LU2＝LV2；

② 如果V1和V2之間存在邊e1，那么U1和U2之間也存在邊e2，且Le1＝Le2；

③如果邊e1上的時間段為Te1，e2上的時間段為Te2，那么Te1和Te2是匹配的。

定義6完全匹配M。給定一個時間圖G，一個查詢圖Q，M?G，令Q的點集為｛V1，V2，…，Vn｝，M的點集為｛U1，U2，…，Un｝，那么M是Q的一個完全匹配需要滿足的條件：

① ?Vi∈Q，?Ui∈M，且LUi＝LVi；

② 如果Vi和Vj之間存在邊ev，那么Ui和Uj之間也存在邊eu，且Lev＝Leu；

③如果邊ev上的時間段為Tev，eu上的時間段為Teu，那么Tev和Teu是匹配的。

根據上述的定義，本文的問題定義為：給定一個查詢圖Q，在時間圖G中找到全部的完全匹配結果，形成結果集R ＝ ｛M1，M2，…，Mn｝。

3 查詢過程

3.1 樸素匹配算法（NM）

樸素匹配算法（Naive Matching）將查詢圖分解成若干個單元查詢圖，并進行單元匹配，而后將單元查詢的結果進行合并。

對圖3（a）所示的是時間圖1 的一個查詢圖，NM算法將其分解成了3 個單元查詢圖，如圖3（b）所示。對單元查詢圖的圖（1）來說，查詢“范新”在3 月7 日的7：00 ～16：30 期間檢修了什么設備，匹配的結果分別為｛｛范新，檢修，設備A，［3 月7 日7：30，3 月7 日8：30］｝，｛范新，檢修，設備B，［3 月7 日16：00，3 月7日16：30］｝｝。單元查詢圖（2）需要查詢2 月5 日之后的相關采購信息，節點均是未知的，根據邊上的關系進行匹配，匹配的結果為｛｛設備B，采購于，公司A，［2月5 日9：00，*］｝，｛設備C，采購于，公司B，［2 月20日10：00，*｝｝。同樣，單元查詢（3）要查詢“王楠”3月7 日9：30 到12：15 之間使用設備的情況，查詢結果為｛｛王楠，使用，設備B，［3 月7 日9：30，3 月7 日10：00］｝，｛王楠，使用，設備C，［3 月7 日10：15，3 月7 日11：00］｝｝。最后，將單元匹配的結果進行合并，最終結果為｛｛范新，檢修，設備B，［3 月7 日16：00，3月7 日16：30］｝，｛設備B，采購于，公司A，［2 月5日9：00，*］，｛王楠，使用，設備B，［3 月7 日9：30，3月7 日10：00］｝｝。很顯然，這種方法需要進行大量的重復匹配，匹配完畢后的合并也需要耗費較多的時間，計算量大，是一種樸素匹配方法。

圖3 查詢圖與單元查詢圖示例

3.2 基于BFS的點匹配算法（BVM）

由于樸素匹配算法需要對單元匹配進行合并，耗時較多，BVM（BFS-Vertex Matching）算法利用了BFS遍歷圖中點的方法依次遍歷查詢圖中的點，在此過程中進行單元匹配。

（1）算法思想。

①選擇一個入度為0 的點，作為初始節點V0。

②在V0和其相鄰點Vi之間進行單元匹配。

③根據BFS算法選擇下一個節點進行單元匹配，直到全部的節點匹配結束。

A l g o r i t h m 1 B V M（G，Q）／ ／G為時間圖，Q為查詢圖1.v i s i t［V 0］＝1；q.p u s h（V 0）；R ＝ ?；2.w h i l e（！q.e m p t y（））｛3.V 1 ＝q.p o p（）；4.f o r每個和V 1相鄰的節點V i｛5.若V 1和V i之間沒有進行過單元匹配，則R ＝U n i t m a p（V 1，V i，e，t）∪R；6.i f（v i s i t［V i］≠1）｛7.q.p u s h（V i）；v i s i t［V i］＝1；8.｝9.｝1 0.｝1 1.r e t u r n R；

（2）實例說明。以圖3（a）的查詢圖為例，對BVM算法進行說明。

①節點“范新”入度為0，作為初始節點，單元查詢圖為圖3（b）中的（1）圖，匹配出“設備A”和“設備B”。

②對單元查詢圖3（b）中的（2）圖進行匹配，根據第一步的匹配結果，查詢圖變更為圖4 所示。

圖4 更新后的查詢圖1

設備A在時間圖中沒有匹配到采購信息，將其刪去。設備B采購于公司A。

③查詢到設備B后，繼續匹配，單元查詢圖如圖5所示。查詢得到“王楠”在3 月7 日9：30 ～10：00 使用了設備B。

圖5 更新后的查詢圖2

BVM算法相較于NM算法而言，BVM算法在匹配過程中就進行了合并，減少了大量不必要的匹配，因而算法執行的效率要高于NM算法。

3.3 拓撲剪枝匹配算法（TPM）

盡管BVM算法運行的效率要高于NM算法，但是在包含大量數據的時間圖中一一進行單元匹配的效率也不高，本節提出一種TPM（Topological Pruning Matching）算法，該算法從拓撲結構和語義角度出發，在匹配過程中進行剪枝，大大加快了查詢的效率。

定義7拓撲單元匹配。對于一個給定的時間圖G，一個單元匹配圖QU，R?G，令QU的點集為｛V1，V2｝，R的點集為｛U1，U2｝，Ui.o 代表節點Ui在時間圖G 中的出度，Ui.i 代表節點Ui在時間圖G 中的入度，Vi.o代表節點Vi在查詢圖Q 中的出度，Vi.i 代表節點Vi在查詢圖Q中的入度，如果R是Q的一個匹配要滿足：

①LU1＝LV1，LU2＝LV2；

② 如果從V1到V2有邊e1，那么從U1到U2也有邊e2，且Le1＝Le2；

③ 對于待查節點Vi，Ui.i≥Vi.i，Ui.o≥Vi.o；

④ 對于待查節點Vi，令EVO和EVi分別為Vi在Q 中所有指出去的邊和指向Vi的邊上關系的集合，EUO和EUi分別為Ui在G 中所有指出去的邊和指向Ui的邊上關系的集合，EVO?EUO，EVi?EUi。

⑤如果邊e1上的時間段為Te1，e2上的時間段為Te2，那么Te1和Te2是匹配的。

（1）算法思想。①選擇一個入度為0 的點，作為初始節點V0；② 在V0和其相鄰點Vi之間進行拓撲單元匹配；③根據BFS算法選擇下一個節點進行拓撲單元匹配，直到全部的節點匹配結束。

（2）索引構建。為了加快算法執行的效率，本文構建了TV-索引和TE-索引，分別用于快速的定位點和邊上的關系，從而提高拓撲單元匹配的速度。圖6、7所示分別為TV-索引和TE-索引結構圖。

圖6 TV-索引結構圖

圖7 TE-索引結構圖

TV-索引是一個類B ＋樹結構的索引。每一個葉子節點由key和ptr兩項組成，其中key表示時間圖中的節點標簽值Vi，ptr指向兩個鏈表，tag 為0 的鏈表中記錄了Vi點所指向的節點Vj情況，包括Vj的標簽值，關系上的時間，以及出入度詳情out-detail 和in-detail。out-detail中記錄了Vj點的出度，以及由Vj指出的邊上的關系，in-detail 中記錄了Vj的入度（除去Vi指向Vj的邊），以及指向Vj的邊上的關系（除去Vi指向Vj的邊上的關系）。tag為1 的鏈表中記錄了指向Vi點的節點情況。每個非葉子節點由key和subptr兩項組成，key是節點的標簽值，用于索引，subptr指向子樹的根節點。

TE-索引能根據邊上的關系查找到連接該邊的兩個節點。具體來說，給定一個關鍵字Pi，計算Pi的hash值，在對應的hash表中找到Pi，Pi中有指針指向鏈表，該鏈表的每一個項集中Si代表節點的標簽，且該節點有指出去的邊，邊上的關系值是Pi，出入度詳情同TV-索引中記錄的內容一致。每一個Si節點都有一個指針指向一個數據塊，記錄了Si節點指向的節點Oi，且Si和Oi之間關系為Pi。在Oi中記錄了Si指向Oi關系的時間段，以及Oi的出入度詳情。

（3）實例說明。以圖3（a）的查詢圖為例，對TPM算法進行說明。

節點“范新”入度為0，作為初始節點。圖3（b）中的（1）圖作為單元查詢圖，做單元拓撲匹配。根據查詢圖3（a），待查節點除去3（b）（1）圖的邊以外，入度和出度都為1，邊上的關系分別為“采購于”和“使用”。根據TV-索引，定位到“范新”，很顯然“設備A”出入度詳情中記錄的數據不符合拓撲單元匹配的要求，最終查找到“設備B”。根據同樣的方法進行下面的匹配。

images/BZ_241_194_1510_1198_1577.png images/BZ_241_194_1577_1198_3267.png

很顯然，加入了拓撲結構和關系上的語義后，使得不符合要求的數據在匹配過程中盡早剔除，大大減少了匹配次數。在TPM 算法中，構建了相關的索引，提高了算法運行的效率。

（4）拓撲單元匹配算法描述。算法2 對拓撲單元匹配算法進行了描述，其中區分了不同的單元查詢圖。

4 實 驗

為了驗證算法的正確性和有效性，本文在8GB 內存、I5-3470 處理器、3.2GB 主頻的計算機上進行了相關實驗。實驗使用了3 個不同數量級大小的模擬數據集，如表1 所示。數據集中的點模擬了人、單位、設備、儀器等對象，邊模擬了對象間的相互關系以及關系的時效。

表1 數據集描述

圖8 所示為NM算法、BVM算法和TPM算法分別在D1、D2 和D3 數據集中運行的結果。從圖8 可見，NM算法消耗的時間最多，BVM 算法次之，TPM 算法消耗的時間最少，這是由于在NM 算法中每次進行單元匹配后均需要合并，消費了大量的時間，TPM 算法在BVM算法的基礎上加上了拓撲結構和邊上語義的匹配，能將不符合條件的中間結果進行剪枝。

圖8 三種算法在不同數據集中對比結果圖

圖9 所示為TPM 算法中確定的模式查詢與Ullmann算法［2］和TCGPM-E 算法［15］進行的對比，從圖中可以看出TPM算法優于Ullmann算法和TCGPME算法的性能，因為Ullmann 算法采用的是深度優先搜索策略，基于點結構的無索引匹配方式，TCGPM-E采用了基于邊結構的圖匹配方式，TPM算法構建了基于拓撲結構和邊上語義的索引，加快了算法的運行效率。

圖9 TPM算法與其他算法對比結果圖

5 結 語

本文利用時間圖匹配技術實現對實驗設備使用、維護、檢修等情況的管理，將設備、單位、人等對象抽象成為時間圖的節點，將使用等信息抽象成為時間圖上的邊和時間區間。本文提出了NM、BVM以及TPM算法用于查詢圖的匹配，并通過實驗對比了3 種方法的性能。實驗結果表明，TPM 的運行效果最好，這是由于TPM算法中運用了拓撲結構和語義匹配，因而能快速地進行剪枝。將TPM算法運用于設備管理，豐富了查詢的語義，提高了查詢效果。