大規(guī)模圖數(shù)據(jù)中緊密子結(jié)構(gòu)查詢系統(tǒng)設(shè)計

◎黃高昂

大規(guī)模圖數(shù)據(jù)中緊密子結(jié)構(gòu)查詢系統(tǒng)設(shè)計

◎黃高昂

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

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

質(zhì)量測量(Quality Measurement)

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

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

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

引入概念—覆蓋率：

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

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

把對于由Q產(chǎn)生的結(jié)果圖集的覆蓋率為α總結(jié)圖 稱為 α-Summary Graph。

基于覆蓋率的質(zhì)量測量更傾向于包含更多關(guān)鍵詞對的結(jié)果圖。

引入概念—總結(jié)尺寸 定義一個總結(jié)圖的尺寸為總結(jié)圖中所含有的全部結(jié)點和邊的數(shù)量總結(jié)圖越小,該圖的簡潔性越好，兩個測量標(biāo)準(zhǔn)結(jié)合到一起。

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

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

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

圖1 Psum算法

XRANK

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

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

關(guān) 鍵 詞ki的v1的rank值： 對于每一個關(guān)鍵詞ki,存在一個v1的子元素或?qū)傩灾祐2,滿足v2 R0而且contains＊(v2,ki).

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

直觀地看出,關(guān)于ki的v1的rank值是ElemRank(v_t)進行適當(dāng)?shù)乜s放來表明結(jié)果的明確性。

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

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

這里f是聚集函數(shù).我們默認(rèn)設(shè)置f=max。

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

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

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

（作者單位：武漢大學(xué) 計算機學(xué)院）