大規模圖數據中緊密子結構查詢系統設計

◎黃高昂

大規模圖數據中緊密子結構查詢系統設計

◎黃高昂

查詢廣泛應用在大數據及圖形數據的查詢，如信息網絡，SOC及知識圖等，由于缺乏結構支持,一次關鍵詞查詢可能會產生過多的結果匹配,一個重要但是容易忽略的任務是將這些查詢結果中具有相似結構或者內容的部分進行總結,如通過向后拓展搜索，雙向擴展搜索，閃爍算法等，可以便于更好地解釋查詢和理解查詢結果。

關鍵詞查詢在查詢圖式數據(社交網絡,知識圖譜,信息網絡)有著廣泛的運用,圖式數據上的查詢是將圖中與查詢的關鍵詞相關的數據進行提取,關鍵詞查詢解釋程序通過對于關鍵詞在圖中提取到的結果圖來將一次關鍵詞查詢轉換為圖結構的查詢。關鍵詞查詢可能會含混不清，圖查詢準確度更高，把關鍵字和圖數據查詢結合起來，可以得到查詢效率度準確度更高的查詢。

質量測量(Quality Measurement)

前提假設結果圖集包含一次關鍵詞查詢中的所有關鍵詞。給定一個關鍵詞對(ki,kj)(ki,kj∈Q ki≠kj) 和由關鍵詞查詢Q產生的結果圖集G。

如果任意在G中的連接關鍵詞vki和vkj的路徑p都能在Gs中找到一條擁有與路徑p

相同標簽的連接vsi和vsj的路徑ps(vki∈[vsi],vkj∈[vsj]),稱總結圖Gs覆蓋了(ki,kj)。

引入概念—覆蓋率：

給定一次關鍵詞查詢和由此產生的結果圖集G,定義結果圖集的總結圖的覆蓋率α為α = 2M / |Q|(|Q| - 1)。

M是Gs所覆蓋的關鍵詞對(k,k’)的總數.注意關鍵詞查詢Q總共的關鍵詞對的數量為|Q|(|Q|-1) 。

把對于由Q產生的結果圖集的覆蓋率為α總結圖 稱為 α-Summary Graph。

基于覆蓋率的質量測量更傾向于包含更多關鍵詞對的結果圖。

引入概念—總結尺寸 定義一個總結圖的尺寸為總結圖中所含有的全部結點和邊的數量總結圖越小,該圖的簡潔性越好，兩個測量標準結合到一起。

定義：Gs是一個最小的α-summary graph。

含義：對于任意其他的α-summary graph Gs’ |Gs|≤ |Gs’|。

優勢關系(Dominance relation) 在結果圖G=(V,E,L)上的一對關鍵詞(k,k’)的優勢關系是在G上中間點的一種二元關系,以至于任意屬于關系R≤(k,k’)的結點對(v1,v2),有L(v1) = L(v2);對于任意一條在關鍵詞k的結點vk1和關鍵詞k’的結點之間且通過結點v1的路徑p1,必存在一條與p1有相同的標簽且通過結點v2連接關鍵詞k的結點vk1’和關鍵詞k’的結點vk2’路徑p2.我們稱對于關鍵詞對(k,k’)v2優勢關系于v1。

圖1 Psum算法

XRANK

概述：與傳統的HTML關鍵詞查詢不同，XML的關鍵詞查詢返回的是包含所請求關鍵詞的深層嵌套的XML元素，而不是返回整個文件。關鍵詞查找是在信息檢索中最有效的范例之一。其中最主要的原因之一是它的簡單性,用戶不用掌握一門復雜的查詢語言,而且可以不需要知曉數據的存儲結構就能進行查詢,XRANK保留簡單的關鍵詞查詢接口,仍在查詢過程中利用XML的標簽和嵌套結構，我們將一組具有超鏈接的XML文件集定義為一個有向圖G=(N,CE,HE) 結點集合N=NE∪NV，其中NE是XML元素的集合,NV是XML值的集合(元素標簽名和屬性名也作為XML值) CE是結點之間包含關系的邊的集合,明確地說,當且僅當v是u的子元素稱邊(u,v)∈CE。HE是結點之間包含超鏈接關系的邊的集合,當且僅當u包含一個指向v的超鏈接則稱邊(u,v)∈HE。(v,u)∈CE：元素u是元素v的子元素 (u,v)∈CE：元素u是元素v的雙親當結點v直接或間接包含關鍵詞k時 定義謂詞＊(v,k)為真假定包含n的關鍵詞的一次關鍵詞查詢Q={k1,k2,k3,..,kn} 令R0={v|v∈NE∧任意k∈Q(contains＊(v,k))}為直接或間接包含查詢中全部關鍵詞的元素集合,則查詢Q的結果定義為 ：

排列函數定義：假定ElemRank(v)是通過XML文件中基礎超鏈接的結構計算出的元素v的客觀重要性,與Google的PageRank算法很相似,不同在于ElemRank是定義在元素的粒度上,并且將XML的嵌套結構加入考量。令一次關鍵詞查詢Q=(k1,k2,k3,…,kn)和它對應的結果R=Result(Q),其中一個結果元素v1(v1∈R) 在定義v1全局的rank值,rank(v1,Q)之前,先定義關于關鍵詞ki的v1的rank值。

關 鍵 詞ki的v1的rank值： 對于每一個關鍵詞ki,存在一個v1的子元素或屬性值v2,滿足v2 R0而且contains＊(v2,ki).

在CE中存在一個包含邊的序列(v1,v2),(v2,v3),…,(v_t,v_t+1)滿 足 v_t+1是一個直接包含關鍵詞ki的結點

直觀地看出,關于ki的v1的rank值是ElemRank(v_t)進行適當地縮放來表明結果的明確性。

decay是一個可以被設置為范圍在0到1直接的值。

上述定義中,我們隠式地假設了關鍵詞ki在v1中只出現一次.如果出現m次,我們首先用上述公式計算每次出現的rank值.設計算出的rank值為r1,r2,r3,…,rm最終組合起來的rank值為

這里f是聚集函數.我們默認設置f=max。

總rank值定義：關于查詢Q=(k1,k2,…,kn)查詢結果元素v1的總rank值為

其中Ne為XML所有元素的總數,Nc(u)是元素u的子元素的個數,E=HE∪CE∪CE^-1,其中CE^-1是包含邊集的反轉集,這個公式沒有將包含邊和超鏈接邊所區分開來,舉一個例子,假設一個含有少部分的包含邊和大量的引用,那么會造成對于每個部分的包含邊會有更少的價值,我們對其進行進一步的改進,將包含邊和超鏈接邊區分開來

本系統是基于Psum算法和Xrank算法，意在讓實驗者理解，掌握Psum和Xrank的工作原理和工作過程中各個部分的功能。結構較為簡單，過程不很復雜，但是實驗精度會受到一定限度，以后應著力提高該實驗的精度。需要說明的是，由于該系統為演示實驗，工作平面無需太大，一臺電腦可以完成。

（作者單位：武漢大學 計算機學院）