1、通過頂點(diǎn)和邊表達(dá)對(duì)象以及對(duì)象間聯(lián)系的圖廣泛應(yīng)用于語義網(wǎng)、生物信息、本體等領(lǐng)域的建模。這些領(lǐng)域的應(yīng)用需要解決百萬量級(jí)規(guī)模以上的圖數(shù)據(jù)處理的可擴(kuò)展性問題。其中，可達(dá)性查詢是判斷傳遞關(guān)系的基本操作，它一般表示為判斷圖上兩個(gè)頂點(diǎn)之間是否存在一條路徑。目前研究的重點(diǎn)是針對(duì)大規(guī)模數(shù)據(jù)應(yīng)用背景，研究壓縮傳遞閉包的索引技術(shù)，以取得索引建立時(shí)間、索引存儲(chǔ)空間和查詢效率之間的優(yōu)化權(quán)衡。本文基本思路是通過拓?fù)渑判驅(qū)D中頂點(diǎn)進(jìn)行層次編號(hào)，再根據(jù)層次編號(hào)在初等數(shù)

2、論方面的性質(zhì)，從每個(gè)頂點(diǎn)的祖先和后代的集合中選取部分頂點(diǎn)建立2-Hop標(biāo)簽，主要貢獻(xiàn)如下:
　　(1)給出標(biāo)簽的形式化定義和理論基礎(chǔ)。對(duì)圖中的頂點(diǎn)引入階的概念，再從每個(gè)頂點(diǎn)的祖先和后代的集合中選取按階遞增的頂點(diǎn)建立2-Hop標(biāo)簽，并對(duì)標(biāo)簽的正確性給出了初等數(shù)論方面的證明。此外，利用初等數(shù)論方面的性質(zhì)，提出了有效地處理跨邊的方式:每一條跨邊的頂點(diǎn)的祖先和后代之間的可達(dá)性關(guān)系只需要增加不超過一個(gè)虛點(diǎn)。
　　(2)設(shè)計(jì)索引的生成算

3、法。引入增序列和減序列的概念，利用增序列和減序列在初等數(shù)論方面的性質(zhì)，提出了高效的標(biāo)簽生成算法，避免了傳遞閉包的計(jì)算。
　　(3)對(duì)標(biāo)簽進(jìn)一步優(yōu)化。使用刪除虛點(diǎn)的方式減小最終生成的標(biāo)簽規(guī)模;提出刪除基于虛邊的高度數(shù)的點(diǎn)的方式，減小建立標(biāo)簽過程中虛點(diǎn)的規(guī)模。
　　(4)在大規(guī)模實(shí)際數(shù)據(jù)集和合成數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，考察索引建立時(shí)間、存儲(chǔ)空間和查詢效率三方面。實(shí)驗(yàn)分析了本文提出的優(yōu)化算法對(duì)性能的影響:刪除虛點(diǎn)的優(yōu)化會(huì)帶來一定的計(jì)算消