基于區(qū)間擴展的可達性查詢算法研究.pdf

1、給定有向無環(huán)圖G，以及圖上的任意兩點u、v?；卮饀是否能夠到達v的可達性查詢是圖的基本操作之一。隨著現(xiàn)代化信息技術(shù)的快速發(fā)展，圖被廣泛應(yīng)用于生物學(xué)、社交網(wǎng)絡(luò)、語義網(wǎng)絡(luò)、模式識別等領(lǐng)域，圖的可達性查詢是圖數(shù)據(jù)管理中的熱點問題之一。大量的學(xué)者投入精力改進可達性查詢算法的效率。但是已存在的可達性查詢算法，由于索引占用空間太大、查詢效率低下等原因，在面對規(guī)模不斷增長的數(shù)據(jù)圖時，效率低、擴展性差。本文從以下幾個方面對可達性查詢問題進行研究。

2、>　　首先，分析現(xiàn)有可達性查詢問題，發(fā)現(xiàn)已有算法構(gòu)建索引時間長，索引占用空間大，查詢效率低下。
　　其次，本文提出線性時間復(fù)雜度的索引構(gòu)建算法，在拓撲排序的過程中，為每個結(jié)點指定相應(yīng)的索引標簽，包含一對互逆的拓撲序號和該結(jié)點在生成樹上的區(qū)間。提出壓縮的索引表示方式，索引的空間復(fù)雜度為 O(n)。提出基于孩子結(jié)點的區(qū)間擴展策略，對于要擴展的結(jié)點u，將其用于覆蓋生成樹上孩子的區(qū)間擴展到圖中覆蓋出鄰居結(jié)點的區(qū)間，增強了回答肯定性可達查詢