發(fā)布時間：2021-03-26 23:19

　　基于標(biāo)簽約束的可達性查詢s→_Lt用于回答給定圖中頂點s到頂點t是否存在路徑標(biāo)簽屬于L的有向路徑.針對現(xiàn)有方法索引構(gòu)建時間長、索引規(guī)模大、查詢效率低的問題,首先基于k個點構(gòu)建雙向路徑標(biāo)簽索引,并提出相應(yīng)的優(yōu)化措施減小索引規(guī)模,以此來加速可達查詢的處理速度.由于其索引沒有完全覆蓋可達查詢,雖然索引規(guī)模小,但仍然無法避免查詢過程中的圖遍歷操作.為此,進一步提出覆蓋所有可達信息的雙向路徑標(biāo)簽索引,基于該索引,查詢處理時可以完全避免圖上的遍歷操作.最后,基于多個真實數(shù)據(jù)集進行測試,實驗結(jié)果從索引大小、索引構(gòu)建時間和查詢響應(yīng)時間方面驗證了所提方法相對現(xiàn)有方法具有索引規(guī)模小、索引時間短且查詢響應(yīng)快的優(yōu)勢. 

【文章來源】：計算機研究與發(fā)展. 2020,57(09)北大核心EICSCD

【文章頁數(shù)】：12 頁

【部分圖文】：

不同規(guī)模數(shù)據(jù)集上的索引大小對比

可達查詢的查詢時間對比

例1. 針對圖1,假設(shè)頂點的處理順序是v2→v4→v3→v5→v1→v0,根據(jù)以上思路建立的索引如表2所示.顯然,這種索引雖然可回答所有查詢,但存在很多冗余路徑,索引規(guī)模過大.例如,inLabel(v4)中同時包含(v0,c),(v0,ac),(v0,bc).當(dāng)給定查詢v0→bv5,outLabel(v0)與inLabel(v5)的交集為{v0,v1,v2,v3,v5},將交集頂點對應(yīng)的標(biāo)簽取并集.對于頂點v0:?∪ab=ab,?∪ac=ac,?∪abc=abc;對于頂點v1:c∪a=ac,c∪ab=abc;對于頂點v2:b∪a=ab,ac∪a=ac;對于頂點v3:ac∪b=abc;對于頂點v5:ab∪?=ab,ac∪?=ac,abc∪?=abc.這些并集標(biāo)簽均不是查詢給定約束標(biāo)簽b的子集,因此v0bv5.顯然,如果查詢不可達,處理效率低.表2 初始路徑標(biāo)簽索引Table 2 The Initial Path Label Index for Fig. 1 Node inLabel outLabel v0 {(v0,?)} {(v0,?),(v1,c),(v2,b),(v2,ac),(v3,ac),(v4,c),(v4,ac),(v4,bc),(v5,ab),(v5,ac),(v5,abc)} v1 {(v0,c),(v1,?)} {(v1,?),(v2,a),(v3,a),(v4,ac),(v5,a),(v5,ab)} v2 {(v0,b),(v0,ac),(v1,a),(v2,?)} {(v2,?),(v4,c),(v5,a)} v3 {(v0,ac),(v1,a),(v3,?)} {(v3,?),(v5,b)} v4 {(v0,c),(v0,ac),(v0,bc),(v1,ac),(v2,c),(v4,?)} {(v4,?)} v5 {(v0,ab),(v0,ac),(v0,abc),(v1,a),(v1,ab),(v2,a),(v3,b),(v5,?)} {(v5,?)} Note: (v,{Lp1,Lp2,…,Lpn}) is organized into {(v,Lp1),(v,Lp2),…,(v,Lpn)}.


本文編號：3102420