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

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

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

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