FLS-一種支持更新的圖可達(dá)性標(biāo)記算法.pdf

1、圖中節(jié)點(diǎn)間的可達(dá)性判定,在現(xiàn)實(shí)中的多個(gè)領(lǐng)域有著廣泛的應(yīng)用,包括知識(shí)表達(dá)、程序分析、地理導(dǎo)航、Internet路由、基于RDF/OWL的本體查詢(xún)、代謝網(wǎng)絡(luò)和XML索引等。
　　 一個(gè)傳統(tǒng)的解決方法是通過(guò)最短路徑算法來(lái)判定節(jié)點(diǎn)間的可達(dá)性,其時(shí)間復(fù)雜度是O(m),其中m=|E|(圖的邊數(shù))。對(duì)于較大的圖來(lái)說(shuō),顯然速度過(guò)慢。
　　 另一個(gè)傳統(tǒng)的解決方法是預(yù)先計(jì)算好圖中節(jié)點(diǎn)間是否可達(dá),也即預(yù)先計(jì)算并存儲(chǔ)圖的傳遞閉包,則可在常數(shù)時(shí)間

2、內(nèi)判定可達(dá)性。然而,其空間復(fù)雜度O(n2)過(guò)大不適用于大圖,且不能有效支持圖的動(dòng)態(tài)更新。
　　 其他的圖可達(dá)性判定算法還有2-HOP,HOPI和DualLabeling,但均不支持被標(biāo)記圖的動(dòng)態(tài)更新,且前兩種算法的時(shí)間復(fù)雜度和空間復(fù)雜度均過(guò)高,不適合應(yīng)用于實(shí)際中。
　　 為有效判定圖中節(jié)點(diǎn)間的可達(dá)性,業(yè)已提出多種對(duì)圖可達(dá)性信息進(jìn)行編碼的節(jié)點(diǎn)標(biāo)記方案,但均無(wú)法有效地支持被標(biāo)記圖的動(dòng)態(tài)更新。針對(duì)這一問(wèn)題,本文提出一種新的分?jǐn)?shù)

3、區(qū)間標(biāo)記方案(FractionalLabelingScheme,FLS)及相應(yīng)的算法,并給出了相關(guān)的理論結(jié)果和實(shí)驗(yàn)結(jié)果,實(shí)驗(yàn)結(jié)果證明FLS能更有效地支持圖的更新并維持與原算法相當(dāng)?shù)臅r(shí)空復(fù)雜度。其特點(diǎn)是采用分?jǐn)?shù)區(qū)間對(duì)節(jié)點(diǎn)作標(biāo)記,在保持根據(jù)判斷區(qū)間大小判斷節(jié)點(diǎn)間可達(dá)性的便捷性上,利用了分?jǐn)?shù)區(qū)間可無(wú)限細(xì)分的特性,使得可以方便處理插入新節(jié)點(diǎn)的操作,圖的其它更新也只需對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行簡(jiǎn)單的調(diào)整,從而有效地支持圖的動(dòng)態(tài)更新。
　　 圖;可達(dá)性