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

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

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