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

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

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

【部分圖文】：

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

可達(dá)查詢的查詢時(shí)間對(duì)比

例1. 針對(duì)圖1,假設(shè)頂點(diǎn)的處理順序是v2→v4→v3→v5→v1→v0,根據(jù)以上思路建立的索引如表2所示.顯然,這種索引雖然可回答所有查詢,但存在很多冗余路徑,索引規(guī)模過大.例如,inLabel(v4)中同時(shí)包含(v0,c),(v0,ac),(v0,bc).當(dāng)給定查詢v0→bv5,outLabel(v0)與inLabel(v5)的交集為{v0,v1,v2,v3,v5},將交集頂點(diǎn)對(duì)應(yīng)的標(biāo)簽取并集.對(duì)于頂點(diǎn)v0:?∪ab=ab,?∪ac=ac,?∪abc=abc;對(duì)于頂點(diǎn)v1:c∪a=ac,c∪ab=abc;對(duì)于頂點(diǎn)v2:b∪a=ab,ac∪a=ac;對(duì)于頂點(diǎn)v3:ac∪b=abc;對(duì)于頂點(diǎn)v5:ab∪?=ab,ac∪?=ac,abc∪?=abc.這些并集標(biāo)簽均不是查詢給定約束標(biāo)簽b的子集,因此v0bv5.顯然,如果查詢不可達(dá),處理效率低.表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)}.


本文編號(hào)：3102420