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

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

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